网络流水题。。Network写成Netword导致WA了两次杯具。
#include <iostream>
using namespace std;
#define N 105
#define INF INT_MAX
int cap[N][N], dis[N], pre[N], cnt[N];
int ISAP(int src, int sink, int n)
{
int maxflow = 0, flow, u = src, v, d;
memset(dis, 0, sizeof(dis));
memset(cnt, 0, sizeof(cnt));
pre[src] = src;
cnt[src] = n;
while(dis[src] < n)
{
if(u == sink)
{
flow = INF;
for(int i = sink; i != src; i = pre[i])
if(cap[pre[i]][i] < flow)
flow = cap[pre[i]][i];
maxflow += flow;
u = src;
for(int i = sink; i != src; i = pre[i])
{
cap[pre[i]][i] -= flow;
cap[i][pre[i]] += flow;
}
}
for(d = n, v = 0; v < n; v++)
{
if(!cap[u][v]) continue;
d = d < dis[v] ? d : dis[v];
if(dis[v] + 1 == dis[u]) break;
}
if(v < n) pre[v] = u, u = v;
else
{
if(!(--cnt[dis[u]])) break;
++cnt[dis[u] = d + 1];
if(u != src) u = pre[u];
}
}
return maxflow;
}
int main()
{
int n, m, st, ed, cas = 1;
while(scanf("%d", &n), n)
{
memset(cap, 0, sizeof(cap));
scanf("%d %d %d", &st, &ed, &m);
for(int i = 0; i < m; i++)
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
a--, b--;
cap[a][b] += c;
cap[b][a] += c;
}
int ans = ISAP(st - 1, ed - 1, n);
printf("Network %d\n", cas++);
printf("The bandwidth is %d.\n\n", ans);
}
return 0;
}