| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
求神犇查错真心不知道问题出哪里了,WA得好惨啊
[CODE]
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<bitset>
using namespace std;
const int N=101,INF=0x3f3f3f3f;
struct Edge{
int to,c,r;
};
vector<Edge> G[N];
bitset<N> used;
inline void addedge(int x,int y,int w){
G[x].push_back((Edge){y,w,G[y].size()});
G[y].push_back((Edge){x,0,G[x].size()-1});
}
int dfs(int s,int t,int now){
if(s==t)
return now;
used.set(s);
for(int i=0;i<G[s].size();i++){
Edge &tmp=G[s][i];
if(!used[tmp.to]&&tmp.c>0){
int new_flow=dfs(tmp.to,t,min(tmp.c,now));
if(new_flow>0){
tmp.c-=new_flow;
G[tmp.to][tmp.r].c+=new_flow;
return new_flow;
}
}
}
return 0;
}
int max_flow(int s,int t){
int ans=0;
while(true){
used.reset();
int new_flow=dfs(s,t,INF);
if(!new_flow) return ans;
else ans+=new_flow;
}
}
int main(){//POJ 1459
int n,np,nc,m;
char c;
while(cin>>n>>np>>nc>>m){
int start=n,end=n+1;
for(int i=0;i<N;i++)
G[i].clear();
for(int i=0,x,y,w;i<m;i++){
cin>>c>>x>>c>>y>>c>>w;
if(x=y) continue;
addedge(x,y,w);
}
for(int i=0,x,w;i<np;i++){
cin>>c>>x>>c>>w;
addedge(start,x,w);
}
for(int i=0,x,w;i<nc;i++){
cin>>c>>x>>c>>w;
addedge(x,end,w);
}
printf("%d\n",max_flow(start,end));
}
return 0;
}//By YOUSIKI
[CPP]
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator