Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

求神犇查错

Posted by yousiki at 2016-04-26 23:13:47 on Problem 1459
真心不知道问题出哪里了,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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator