Detail of message

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

HELP!!DFS找增广路WA，BFS就AC是为啥（附代码）

Posted by newbin at 2019-04-29 21:08:40 on Problem 3436

DFS版：
#include<iostream>
#include<cstdio>
#include<string.h>
#include<queue>
#define ll long long
using namespace std;
const int maxn = 505;
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct node{
	int u,v,nxt;
	ll f;
}e[maxn*maxn*2];
int cnt = 0;
int head[maxn];
void add(int u,int v,ll f){
	e[cnt].u = u;
	e[cnt].v = v;
	e[cnt].f = f;
	e[cnt].nxt = head[u];
	head[u] = cnt++;
}
int s[maxn][20],t[maxn][20];
ll w[maxn];
int p,n;
int mp[maxn][maxn];
bool ju(int u,int v){
	bool ok = true;
	for(int i = 0;i < p;++i){
		if(t[u][i] == 0 && s[v][i] == 1) ok = false;
		if(t[u][i] == 1 && s[v][i] == 0) ok = false;
	}return ok;
}
void init(){
	cnt = 0;
	memset(head,-1,sizeof head);
	for(int i = 0;i <= n;++i) {
		for(int j = 0;j <= n;++j) mp[i][j] = 0;
	}
	for(int i = 1;i <= n;++i){
		scanf("%lld",&w[i]);
		int ok = 1;
		for(int j = 0;j < p;++j) {
			scanf("%d",&s[i][j]);
			if(s[i][j] == 1) ok = 0;
		}
		if(ok) add(0,i,w[i]),add(i,0,0);
		ok = 1;
		for(int j = 0;j < p;++j){
			scanf("%d",&t[i][j]);
			if(t[i][j] == 0) ok = 0;
		}
		if(ok) add(i,n+1,w[i]),add(n+1,i,0);
	}
	for(int i = 1;i <= n;++i){
		for(int j = i+1;j <= n;++j){
			if(ju(i,j)) add(i,j,w[i]),add(j,i,0);
			if(ju(j,i)) add(j,i,w[j]),add(i,j,0);
		}
	}
}
int pre[maxn];
int vis[maxn]={0};
bool dfs(int u){
	vis[u] = 1;
	if(u == n+1) return true;
	for(int i = head[u];i != -1;i = e[i].nxt){
		int v = e[i].v;
		if(vis[v]) continue;
		if(e[i].f == 0) continue;
		pre[v] = i;
		if(dfs(v)) return true;
	}
	return false;
}
void sol(){
	ll ans = 0;
	int tot = 0;
	memset(pre,-1,sizeof pre);
	while(dfs(0)){
		for(int i = 0;i <= n+1;++i) vis[i] = 0;
		ll d = inf;
		int u,v;
		v = n+1;
		while(v!=0){
			u = e[pre[v]].u;
			d = min(d,e[pre[v]].f);
			v = u;
		}
		v = n+1;
		while(v != 0){
			u = e[pre[v]].u;
			if(pre[v]&1) mp[u][v]-=d;
			else mp[u][v]+=d;
			e[pre[v]].f -= d;
			e[pre[v]^1].f += d;//给反向边加上回流 
			v = u;
		}
		ans += d;
	}
	cout<<ans<<" ";
	int num = 0;
	for(int i = 1;i <= n;++i){
		for(int j = 1;j <= n;++j) if(mp[i][j]) num++;
	}
	cout<<num<<endl;
	for(int i = 1;i <= n;++i){
		for(int j = 1;j <= n;++j) if(mp[i][j]) cout<<i<<" "<<j<<" "<<mp[i][j]<<endl;
	}
}
int main(){
	while(~scanf("%d%d",&p,&n)) init(),sol();
} 

BFS版：
#include<iostream>
#include<cstdio>
#include<string.h>
#include<queue>
#define ll long long
using namespace std;
const int maxn = 505;
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct node{
	int u,v,nxt;
	ll f;
}e[maxn*maxn*2];
int cnt = 0;
int head[maxn];
void add(int u,int v,ll f){
	e[cnt].u = u;
	e[cnt].v = v;
	e[cnt].f = f;
	e[cnt].nxt = head[u];
	head[u] = cnt++;
}
int s[maxn][20],t[maxn][20];
ll w[maxn];
int p,n;
int mp[maxn][maxn];
bool ju(int u,int v){
	bool ok = true;
	for(int i = 0;i < p;++i){
		if(t[u][i] == 0 && s[v][i] == 1) ok = false;
		if(t[u][i] == 1 && s[v][i] == 0) ok = false;
	}return ok;
}
void init(){
	cnt = 0;
	memset(head,-1,sizeof head);
	for(int i = 0;i <= n;++i) {
		for(int j = 0;j <= n;++j) mp[i][j] = 0;
	}
	for(int i = 1;i <= n;++i){
		scanf("%lld",&w[i]);
		int ok = 1;
		for(int j = 0;j < p;++j) {
			scanf("%d",&s[i][j]);
			if(s[i][j] == 1) ok = 0;
		}
		if(ok) add(0,i,w[i]),add(i,0,0);
		ok = 1;
		for(int j = 0;j < p;++j){
			scanf("%d",&t[i][j]);
			if(t[i][j] == 0) ok = 0;
		}
		if(ok) add(i,n+1,w[i]),add(n+1,i,0);
	}
	for(int i = 1;i <= n;++i){
		for(int j = i+1;j <= n;++j){
			if(ju(i,j)) add(i,j,w[i]),add(j,i,0);
			if(ju(j,i)) add(j,i,w[j]),add(i,j,0);
		}
	}
}
int pre[maxn];
int vis[maxn]={0};
bool bfs(){
	for(int i = 0;i <= n+1;++i) vis[i] = 0;
	queue<int> q;q.push(0);vis[0] = 1;
	while(q.size()){
		int u = q.front();q.pop();
		for(int i = head[u];i!=-1;i = e[i].nxt){
			int v = e[i].v;
			if(vis[v]) continue;
			if(e[i].f == 0) continue;
			vis[v] = 1;
			pre[v] = i;
			q.push(v);
		}
	}
	return vis[n+1];
}
void sol(){
	ll ans = 0;
	int tot = 0;
	memset(pre,-1,sizeof pre);
	while(bfs()){
		ll d = inf;
		int u,v;
		v = n+1;
		while(v!=0){
			u = e[pre[v]].u;
			d = min(d,e[pre[v]].f);
			v = u;
		}
		v = n+1;
		while(v != 0){
			u = e[pre[v]].u;
			if(pre[v]&1) mp[u][v]-=d;
			else mp[u][v]+=d;
			e[pre[v]].f -= d;
			e[pre[v]^1].f += d;//给反向边加上回流 
			v = u;
		}
		ans += d;
	}
	cout<<ans<<" ";
	int num = 0;
	for(int i = 1;i <= n;++i){
		for(int j = 1;j <= n;++j) if(mp[i][j]) num++;
	}
	cout<<num<<endl;
	for(int i = 1;i <= n;++i){
		for(int j = 1;j <= n;++j) if(mp[i][j]) cout<<i<<" "<<j<<" "<<mp[i][j]<<endl;
	}
}
int main(){
	while(~scanf("%d%d",&p,&n)) init(),sol();
} 

刚开始学网络流，求教ORZ

Followed by:

Post your reply here:

User ID:
Password:
Title:

Content:

> DFS版：
> #include<iostream>
> #include<cstdio>
> #include<string.h>
> #include<queue>
> #define ll long long
> using namespace std;
> const int maxn = 505;
> const ll inf = 0x3f3f3f3f3f3f3f3f;
> struct node{
> 	int u,v,nxt;
> 	ll f;
> }e[maxn*maxn*2];
> int cnt = 0;
> int head[maxn];
> void add(int u,int v,ll f){
> 	e[cnt].u = u;
> 	e[cnt].v = v;
> 	e[cnt].f = f;
> 	e[cnt].nxt = head[u];
> 	head[u] = cnt++;
> }
> int s[maxn][20],t[maxn][20];
> ll w[maxn];
> int p,n;
> int mp[maxn][maxn];
> bool ju(int u,int v){
> 	bool ok = true;
> 	for(int i = 0;i < p;++i){
> 		if(t[u][i] == 0 && s[v][i] == 1) ok = false;
> 		if(t[u][i] == 1 && s[v][i] == 0) ok = false;
> 	}return ok;
> }
> void init(){
> 	cnt = 0;
> 	memset(head,-1,sizeof head);
> 	for(int i = 0;i <= n;++i) {
> 		for(int j = 0;j <= n;++j) mp[i][j] = 0;
> 	}
> 	for(int i = 1;i <= n;++i){
> 		scanf("%lld",&w[i]);
> 		int ok = 1;
> 		for(int j = 0;j < p;++j) {
> 			scanf("%d",&s[i][j]);
> 			if(s[i][j] == 1) ok = 0;
> 		}
> 		if(ok) add(0,i,w[i]),add(i,0,0);
> 		ok = 1;
> 		for(int j = 0;j < p;++j){
> 			scanf("%d",&t[i][j]);
> 			if(t[i][j] == 0) ok = 0;
> 		}
> 		if(ok) add(i,n+1,w[i]),add(n+1,i,0);
> 	}
> 	for(int i = 1;i <= n;++i){
> 		for(int j = i+1;j <= n;++j){
> 			if(ju(i,j)) add(i,j,w[i]),add(j,i,0);
> 			if(ju(j,i)) add(j,i,w[j]),add(i,j,0);
> 		}
> 	}
> }
> int pre[maxn];
> int vis[maxn]={0};
> bool dfs(int u){
> 	vis[u] = 1;
> 	if(u == n+1) return true;
> 	for(int i = head[u];i != -1;i = e[i].nxt){
> 		int v = e[i].v;
> 		if(vis[v]) continue;
> 		if(e[i].f == 0) continue;
> 		pre[v] = i;
> 		if(dfs(v)) return true;
> 	}
> 	return false;
> }
> void sol(){
> 	ll ans = 0;
> 	int tot = 0;
> 	memset(pre,-1,sizeof pre);
> 	while(dfs(0)){
> 		for(int i = 0;i <= n+1;++i) vis[i] = 0;
> 		ll d = inf;
> 		int u,v;
> 		v = n+1;
> 		while(v!=0){
> 			u = e[pre[v]].u;
> 			d = min(d,e[pre[v]].f);
> 			v = u;
> 		}
> 		v = n+1;
> 		while(v != 0){
> 			u = e[pre[v]].u;
> 			if(pre[v]&1) mp[u][v]-=d;
> 			else mp[u][v]+=d;
> 			e[pre[v]].f -= d;
> 			e[pre[v]^1].f += d;//给反向边加上回流 
> 			v = u;
> 		}
> 		ans += d;
> 	}
> 	cout<<ans<<" ";
> 	int num = 0;
> 	for(int i = 1;i <= n;++i){
> 		for(int j = 1;j <= n;++j) if(mp[i][j]) num++;
> 	}
> 	cout<<num<<endl;
> 	for(int i = 1;i <= n;++i){
> 		for(int j = 1;j <= n;++j) if(mp[i][j]) cout<<i<<" "<<j<<" "<<mp[i][j]<<endl;
> 	}
> }
> int main(){
> 	while(~scanf("%d%d",&p,&n)) init(),sol();
> } 
> 
> BFS版：
> #include<iostream>
> #include<cstdio>
> #include<string.h>
> #include<queue>
> #define ll long long
> using namespace std;
> const int maxn = 505;
> const ll inf = 0x3f3f3f3f3f3f3f3f;
> struct node{
> 	int u,v,nxt;
> 	ll f;
> }e[maxn*maxn*2];
> int cnt = 0;
> int head[maxn];
> void add(int u,int v,ll f){
> 	e[cnt].u = u;
> 	e[cnt].v = v;
> 	e[cnt].f = f;
> 	e[cnt].nxt = head[u];
> 	head[u] = cnt++;
> }
> int s[maxn][20],t[maxn][20];
> ll w[maxn];
> int p,n;
> int mp[maxn][maxn];
> bool ju(int u,int v){
> 	bool ok = true;
> 	for(int i = 0;i < p;++i){
> 		if(t[u][i] == 0 && s[v][i] == 1) ok = false;
> 		if(t[u][i] == 1 && s[v][i] == 0) ok = false;
> 	}return ok;
> }
> void init(){
> 	cnt = 0;
> 	memset(head,-1,sizeof head);
> 	for(int i = 0;i <= n;++i) {
> 		for(int j = 0;j <= n;++j) mp[i][j] = 0;
> 	}
> 	for(int i = 1;i <= n;++i){
> 		scanf("%lld",&w[i]);
> 		int ok = 1;
> 		for(int j = 0;j < p;++j) {
> 			scanf("%d",&s[i][j]);
> 			if(s[i][j] == 1) ok = 0;
> 		}
> 		if(ok) add(0,i,w[i]),add(i,0,0);
> 		ok = 1;
> 		for(int j = 0;j < p;++j){
> 			scanf("%d",&t[i][j]);
> 			if(t[i][j] == 0) ok = 0;
> 		}
> 		if(ok) add(i,n+1,w[i]),add(n+1,i,0);
> 	}
> 	for(int i = 1;i <= n;++i){
> 		for(int j = i+1;j <= n;++j){
> 			if(ju(i,j)) add(i,j,w[i]),add(j,i,0);
> 			if(ju(j,i)) add(j,i,w[j]),add(i,j,0);
> 		}
> 	}
> }
> int pre[maxn];
> int vis[maxn]={0};
> bool bfs(){
> 	for(int i = 0;i <= n+1;++i) vis[i] = 0;
> 	queue<int> q;q.push(0);vis[0] = 1;
> 	while(q.size()){
> 		int u = q.front();q.pop();
> 		for(int i = head[u];i!=-1;i = e[i].nxt){
> 			int v = e[i].v;
> 			if(vis[v]) continue;
> 			if(e[i].f == 0) continue;
> 			vis[v] = 1;
> 			pre[v] = i;
> 			q.push(v);
> 		}
> 	}
> 	return vis[n+1];
> }
> void sol(){
> 	ll ans = 0;
> 	int tot = 0;
> 	memset(pre,-1,sizeof pre);
> 	while(bfs()){
> 		ll d = inf;
> 		int u,v;
> 		v = n+1;
> 		while(v!=0){
> 			u = e[pre[v]].u;
> 			d = min(d,e[pre[v]].f);
> 			v = u;
> 		}
> 		v = n+1;
> 		while(v != 0){
> 			u = e[pre[v]].u;
> 			if(pre[v]&1) mp[u][v]-=d;
> 			else mp[u][v]+=d;
> 			e[pre[v]].f -= d;
> 			e[pre[v]^1].f += d;//给反向边加上回流 
> 			v = u;
> 		}
> 		ans += d;
> 	}
> 	cout<<ans<<" ";
> 	int num = 0;
> 	for(int i = 1;i <= n;++i){
> 		for(int j = 1;j <= n;++j) if(mp[i][j]) num++;
> 	}
> 	cout<<num<<endl;
> 	for(int i = 1;i <= n;++i){
> 		for(int j = 1;j <= n;++j) if(mp[i][j]) cout<<i<<" "<<j<<" "<<mp[i][j]<<endl;
> 	}
> }
> int main(){
> 	while(~scanf("%d%d",&p,&n)) init(),sol();
> } 
> 
> 刚开始学网络流，求教ORZ

Home Page Go Back To top