第一次實作最大流,結果WA
不知道哪裡錯了或沒注意到
麻煩大大們幫我看一下 感激
#include <cstdio>
#include <queue>
#define min(a,b) ((a) < (b) ? (a) : (b))
using namespace std;
int E[100][100];
int E_C[100];
int R[100][100];
int BFS(int s,int t,int P[]){
int F[100];
bool fg[100] = {0};
queue<int> q;
fg[s] = 1;
F[s] = 2e9;
q.push(s);
while(!q.empty()){
int v = q.front();
q.pop();
for(int i = 0,u;i < E_C[v];i++){
u = E[v][i];
if(!fg[u] && R[v][u] > 0){
fg[u] = 1;
F[u] = min(F[v],R[v][u]);
P[u] = v;
if(u == t)
return F[u];
q.push(u);
}
}
}
return 0;
}
int main(){
int Q = 1;
int N;
while(1){
scanf("%d",&N);
if(N == 0)return 0;
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
R[i][j] = 0;
for(int i = 0;i < N;i++)
E_C[i] = 0;
int S,T,CC;
scanf("%d %d %d",&S,&T,&CC);
for(int i = 0,u,v,w;i < CC; i++){
scanf("%d %d %d",&u,&v,&w);
u--;
v--;
R[u][v] += w;
R[v][u] += w;
E[u][E_C[u]] = v ;
E[v][E_C[v]] = u;
E_C[u]++;
E_C[v]++;
}
int Ans = 0;
int tt;
int P[100];
S--;
T--;
while(1){
tt = BFS(S,T,P);
if (tt == 0)break;
for(int v = T;v != S;v = P[v]){
R[P[v]][v] -= tt;
R[v][P[v]] += tt;
}
Ans += tt;
}
printf("Network %d\nThe bandwidth is %d.\n\n",Q++,Ans);
}
}
第一次實作最大流,結果WA
不知道哪裡錯了或沒注意到
麻煩大大們幫我看一下 感激
#include
#include
#define min(a,b) ((a) < (b) ? (a) : (b))
using namespace std;
int E[100][100];
int E_C[100];
int R[100][100];
int BFS(int s,int t,int P[]){
int F[100];
bool fg[100] = {0};
queue q;
fg[s] = 1;
F[s] = 2e9;
q.push(s);
while(!q.empty()){
int v = q.front();
q.pop();
for(int i = 0,u;i < E_C[v];i++){
u = E[v][i];
if(!fg[u] && R[v][u] > 0){
fg[u] = 1;
F[u] = min(F[v],R[v][u]);
P[u] = v;
if(u == t)
return F[u];
q.push(u);
}
}
}
return 0;
}
int main(){
int Q = 1;
int N;
while(1){
scanf("%d",&N);
if(N == 0)return 0;
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
R[i][j] = 0;
for(int i = 0;i < N;i++)
E_C[i] = 0;
int S,T,CC;
scanf("%d %d %d",&S,&T,&CC);
for(int i = 0,u,v,w;i < CC; i++){
scanf("%d %d %d",&u,&v,&w);
u--;
v--;
R[u][v] += w;
R[v][u] += w;
E[u][E_C[u]] = v ;
E[v][E_C[v]] = u;
E_C[u]++;
E_C[v]++;
}
int Ans = 0;
int tt;
int P[100];
S--;
T--;
while(1){
tt = BFS(S,T,P);
if (tt == 0)break;
for(int v = T;v != S;v = P[v]){
R[P[v]][v] -= tt;
R[v][P[v]] += tt;
}
Ans += tt;
}
printf("Network %d\nThe bandwidth is %d.\n\n",Q++,Ans);
}
}
貌似是E那個陣列的第二個維度開太小了,
我只能說這題的測資質真的不是普通的陰險= ="