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");
}
。。。国 庆就去看看廖远古神牛的推荐
呵呵，有事情干了~~