多源点汇点的网络流最大流问题。
注意题目要求顶点编号从0开始。我是用SAP算法来做的，用时766ms；EdmondsKarp算法用时1610ms。
以下是我的代码：
#include<iostream>
#include<sstream>
#include<string>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
const int kMaxn(107);
const int kInf(0x7f7f7f7f);
int n,np,nc,m,s,t,c[kMaxn][kMaxn];
int maxflow,f[kMaxn][kMaxn];
void SAP()
{
int d[kMaxn],num[kMaxn],p[kMaxn];
memset(f,0,kMaxn*kMaxn*sizeof(int));
memset(d,0x7f,kMaxn*sizeof(int));
memset(num,0,kMaxn*sizeof(int));
queue<int> q;
d[t]=0;
num[0]++;
q.push(t);
while(!q.empty())
{
int v(q.front());q.pop();
for(int u=0;u<n;u++)
if(d[u]>=n && c[u][v]>f[u][v])
{
d[u]=d[v]+1;
num[d[u]]++;
q.push(u);
}
}
maxflow=0;
int u(s),v;
while(d[s]<n)
{
v=-1;
for(int i=0;i<n;i++)
if(c[u][i]>f[u][i] && d[u]==d[i]+1)
{v=i;break;}
if(v!=-1)
{
p[v]=u;u=v;
if(u==t)
{
int add(kInf);
for(u=t;u!=s;u=p[u])
add=min(add,c[p[u]][u]-f[p[u]][u]);
maxflow+=add;
for(u=t;u!=s;u=p[u])
{
f[p[u]][u]+=add;
f[u][p[u]]-=add;
}
}
}
else
{
num[d[u]]--;
if(!num[d[u]])
return;
d[u]=n;
for(v=0;v<n;v++)
if(c[u][v]>f[u][v])
d[u]=min(d[u],d[v]+1);
num[d[u]]++;
if(u!=s)
u=p[u];
}
}
}
int main()
{
while(scanf("%d%d%d%d",&n,&np,&nc,&m)==4)
{
s=n;
t=n+1;
n+=2;
memset(c,0,kMaxn*kMaxn*sizeof(int));
for(int i=1;i<=m;i++)
{
string in;
cin>>in;
for(int j=0;j<in.size();j++)
if(!isdigit(in[j]))
in[j]=' ';
istringstream sin(in);
int u,v,w;
sin>>u>>v>>w;
c[u][v]+=w;
}
for(int i=1;i<=np;i++)
{
string in;
cin>>in;
for(int j=0;j<in.size();j++)
if(!isdigit(in[j]))
in[j]=' ';
istringstream sin(in);
int u,v;
sin>>u>>v;
c[s][u]+=v;
}
for(int i=1;i<=nc;i++)
{
string in;
cin>>in;
for(int j=0;j<in.size();j++)
if(!isdigit(in[j]))
in[j]=' ';
istringstream sin(in);
int u,v;
sin>>u>>v;
c[u][t]+=v;
}
SAP();
printf("%d\n",maxflow);
}
return 0;
}
posted on 2011-05-30 16:21
lee1r 阅读(165)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论