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

## 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;
e[cnt].u = u;
e[cnt].v = v;
e[cnt].f = f;
}
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;
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;
}
ok = 1;
for(int j = 0;j < p;++j){
scanf("%d",&t[i][j]);
if(t[i][j] == 0) ok = 0;
}
}
for(int i = 1;i <= n;++i){
for(int j = i+1;j <= n;++j){
}
}
}
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;
e[cnt].u = u;
e[cnt].v = v;
e[cnt].f = f;
}
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;
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;
}
ok = 1;
for(int j = 0;j < p;++j){
scanf("%d",&t[i][j]);
if(t[i][j] == 0) ok = 0;
}
}
for(int i = 1;i <= n;++i){
for(int j = i+1;j <= n;++j){
}
}
}
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();
}

```

Followed by: