UVA（820）：互聯網帶寬得到錯誤的答案？

-1

我想解決這個Problem關於UVA。問題是關於找到圖中的最大流量。我使用了Edmond-karp算法，但是我一直在錯誤的答案。任何人都可以告訴我我的代碼中出現了什麼問題？我的代碼：UVA（820）：互聯網帶寬得到錯誤的答案？

#include<bits/stdc++.h> 
using namespace std; 
#define MX 1000000007 
#define LL long long 
#define ri(x) scanf("%d",&x) 
#define rl(x) scanf("%lld",&x) 
#define len(x) x.length() 
#define FOR(i,a,n) for(int i=a;i<n;i++) 
#define FORE(i,a,n) for(int i=a;i<=n;i++) 
template<class T1> inline T1 maxi(T1 a,T1 b){return a>b?a:b;} 
template<class T2> inline T2 mini(T2 a,T2 b){return a<b?a:b;} 
int parent[101],G[101][101],rG[101][101]; 
bool bfs(int s,int t,int n) 
{ 
    bool vis[n+2]; 
    memset(parent,0,sizeof parent); 
    memset(vis,0,sizeof vis); 
    queue<int>Q; 
    Q.push(s); 
    vis[s]=true; 
    while(!Q.empty()) 
    { 
     int fnt=Q.front(); 
     Q.pop(); 
     for(int v=1;v<=n;v++) 
     { 
      if(!vis[v] and G[fnt][v]>0) 
      { 
       vis[v]=true; 
       parent[v]=fnt; 
       Q.push(v); 
      } 
     } 
    } 
    return vis[t]; 
} 
int main() 
{ 
    int n,tst=1; 
    ri(n); 
    while(n) 
    { 
     int s,t,c,flow=0; 
     ri(s),ri(t),ri(c); 
     FORE(i,1,c) 
     { 
      int x,y,z; 
      ri(x),ri(y),ri(z); 
      G[x][y]+=z; 
      G[y][x]+=z; 
     } 
     while(bfs(s,t,n)) 
     { 
      int path=9999999; 
      for(int v=t;v!=s;v=parent[v]) 
      { 
       int u=parent[v]; 
       path=mini(path,G[u][v]); 
      } 
      for(int v=t;v!=s;v=parent[v]) 
      { 
       int u=parent[v]; 
       G[u][v]-=path; 
       G[v][u]+=path; 
      } 
      flow+=path; 
     }  
     printf("Network %d\nThe bandwidth is %d.\n\n", tst++, flow); 
     ri(n); 
    } 
}

來源

2015-09-14 Krishna Sai

我討厭關於UVA的問題陳述，因爲他們通常沒有給出足夠清晰的限制。在這個問題中，你是否確定最大流量不能溢出？您可以在一對節點之間有多條邊，理論上最大流量可以溢出。 –

這不是一個調試服務。縮小問題範圍並提出更具體的問題。至少給我們一個失敗的案例。 – IVlad

你推流周圍的其他方法：

G[u][v]-=path; 
G[v][u]+=path;

這應該是：

G[u][v] += path; 
G[v][u] -= path;

此外，我不知道這部分：

if(!vis[v] and G[fnt][v]>0) 

[...] 

path=mini(path,G[u][v]);

因爲你是也允許採取流量爲負的路徑。你不應該改變G，這似乎是你的容量圖。相反，你應該有一個矩陣F存儲你發送的流量。那麼你的兩個條件應改爲：

if (!vis[v] && G[fnt][v] != F[fnt][v]) 

[...] 

path = mini(path, G[u][v] - F[u][v])

，推動流程上F，不G。

自從您聲明矩陣rG以來，您似乎已經考慮過這個問題，但您從未使用過它。

也可能有其他問題。不知道你遇到了什麼問題很難說清楚。

來源

2015-09-14 16:14:41 IVlad

UVA（820）：互聯網帶寬得到錯誤的答案？

回答

相關問題