boat's Blog

swain[王雨舟](394528923) 22: wudiswain[王雨舟](394528923) 22:25:50
一张地图上，有一些矿点，每个矿点上都一个一定数量的矿（每个矿的量不一定相同） ，图上有些点可能是障碍物，现在坦克从图的左上角出发，出口在右下角，坦克只能往右或者往下开，问最多能有得到多少矿点，坦克开过矿点后矿点的矿全部给坦克
wudisplay[bsed刘通](357240143) 22:26:17
费用流？
wudiswain[王雨舟](394528923) 22:26:20
各位大牛，赶紧秒杀了这个。。
wudiswain[王雨舟](394528923) 22:26:34
。。费..
wudisplay[bsed刘通](357240143) 22:26:41
没描述啊
wudiswain[王雨舟](394528923) 22:26:51
坦克从图的左上角出发，出口在右下角，坦克只能往右或者往下开
wudisplay[bsed刘通](357240143) 22:27:06
DP就行了吧？
wudiswain[王雨舟](394528923) 22:27:11
恩
wudiswain[王雨舟](394528923) 22:27:15
这是问题一
wudiswain[王雨舟](394528923) 22:27:26
还有改进版的
wudiswain[王雨舟](394528923) 22:27:33
现在图上有一些传送门
wudisplay[bsed刘通](357240143) 22:27:32

wudiswain[王雨舟](394528923) 22:27:44
每个传送门指定到图上 的一个点
wudiswain[王雨舟](394528923) 22:27:54
现在问你最多能有多少矿
wudiswain[王雨舟](394528923) 22:28:14
各位观众赶紧来秒杀这个
wudisplay[bsed刘通](357240143) 22:28:21
擦，这不是你问过小红的嘛
wudiswain[王雨舟](394528923) 22:28:39
。。擦，我哈尔滨回来后今天花了一天才AC
wudisplay[bsed刘通](357240143) 22:28:58
这种题，给他们说有意义么...反正我不会
wudiwudiswain[王雨舟](394528923) 22:29:31
。。我只是想说，不搞ACM的话，类似这种东西是很难写的。。
wudisplay[bsed刘通](357240143) 22:29:36

wudiswain[王雨舟](394528923) 22:29:47
刘大牛。。你怎么可能不会
wudisplay[bsed刘通](357240143) 22:29:48
果然比我有远见
wudiswain[王雨舟](394528923) 22:30:25
我只是想让听众有点兴趣而已
wudiswain[王雨舟](394528923) 22:30:37
方帧去哪了

先将所有矿点缩点，然后求最长路

//boatswain 2010 /10/ 1
//*********************************
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N=25000;
int n,m,ans;
char map[50][50];
int loc[50][50];
int door[N];
int doornum;
int block[N];
int blocknum;
int ore[N];
int orenum;
//tarjan()
int scc,index,dfn[N],low[N],belong[N],num[N],sstack[N],top,out[N];
bool instack[N];
struct Edge{
	int v,next;
}edge[N];
int cnt;
int head[N];
int sum[N];
bool oyes(int i,int j){
	if (i>=0&&i<n&&j>=0&&j<m&&map[i][j]!='#')	return true;
	return false;
}
void addedge(int u,int v){
	edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++;
}
struct Edge2{
	int v,next,val;
}e[N];
int aug;
int head2[N];
void addedge2(int u,int v,int val){
	e[aug].v=v;
	e[aug].val=val;
	e[aug].next=head2[u];
	head2[u]=aug++;
}
void init(){
	aug=cnt=doornum=blocknum=orenum=0;
	memset(head,-1,sizeof(head));
	memset(head2,-1,sizeof(head));
	memset(block,0,sizeof(block));
	memset(loc,0,sizeof(loc));
	memset(map,0,sizeof(map));
	memset(ore,0,sizeof(ore));
	scanf("%d%d",&n,&m);
	for (int i=0;i<n;i++)  scanf("%s",map[i]);
	for (int i=0;i<n;i++)	
		for (int j=0;j<m;j++){
			loc[i][j]=i*m+j;
			if (map[i][j]=='*')		door[doornum++]=i*m+j;
			else if (map[i][j]=='#')	block[blocknum++]=i*m+j;
			else ore[loc[i][j]]=map[i][j]-'0';
		}
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++){
			if (!oyes(i,j)) continue;
			if (oyes(i+1,j)) addedge(loc[i][j],loc[i+1][j]);
			if (oyes(i,j+1)) addedge(loc[i][j],loc[i][j+1]);
		}
	for (int i=0;i<doornum;i++){
		int a,b;	scanf("%d%d",&a,&b);
		if (oyes(a,b)) addedge(door[i],loc[a][b]);
	}
}
int MAX(int a,int b){
    if (a<b) return b;
    return a;
}
int MIN(int a,int b){
    if(a<b)
        return a;
    return b;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++index;
    sstack[++top]=u;
    instack[u]=true;
    for (int j=head[u];j!=-1;j=edge[j].next){
        int v=edge[j].v;
        if(dfn[v]==0){
            tarjan(v);
            low[u]=MIN(low[u],low[v]);
        }
        else if(instack[v])
        {
            low[u]=MIN(low[u],dfn[v]);
        }  
    }
    if(dfn[u]==low[u])
    {
        scc++;
        while(1)
        {
            int tmp=sstack[top--];
            instack[tmp]=0;
            belong[tmp]=scc;
            num[scc]++;
            if(tmp==u)
                break;
        }
    }
}
void SPFA(){
		bool vis[N];
		int dist[N],l,r,q[N*10],MAXQ=N+5;
		for (int i=0;i<scc+1;i++){
			dist[i]=-1;
			vis[i]=false;
		}
		l=r=0;
		q[r++]=0;
		dist[0]=0;
		while (l!=r){
			int u=q[l++];l%=MAXQ;
			vis[u]=false;
			for (int j=head2[u];j!=-1;j=e[j].next){
				int v=e[j].v;
				if (dist[v]<dist[u]+e[j].val){
					dist[v]=dist[u]+e[j].val;
				    if (!vis[v]){             
                       vis[v]=true; q[r++]=v;r%=MAXQ;
                       }
                }
		}
		}
		ans=0;
		for (int i=1;i<scc+1;i++){
            ans=MAX(ans,dist[i]);
            }
			
}
void solve(){
	scc=top=index=0;
	memset(dfn,0,sizeof(dfn));
	memset(sum,0,sizeof(sum));
	for (int i=0;i<n*m;i++)
		if (!dfn[i]) tarjan(i);
	for (int i=0;i<n*m;i++)
		sum[belong[i]]+=ore[i];
	addedge2(0,belong[0],sum[belong[0]]);
	for (int i=0;i<n*m;i++){
		for (int j=head[i];j!=-1;j=edge[j].next){
			int v=edge[j].v;
			if (belong[i]!=belong[v])
				addedge2(belong[i],belong[v],sum[belong[v]]);
		}
	}
 SPFA();
}
void output(){
	printf("%d\n",ans);
}
int main(){
   // freopen("a.in","r",stdin);
	int T;
	scanf("%d",&T);
	while(T--){
		init();
		solve();
		output();
	}
	system("PAUSE");
}