这题的题意是给出n的点,每个点有容量限制,然后给出每条边的运输的容量,问你从XX城市运送电量到YY城市最大的电量是多少。。
最大流的模板题,直接用EK算法。。XX城市设定0,YY城市为n+1。还有一点要注意的是在求最小的残量的是还要看每个顶点容量。。
#include#include #include #include #include using namespace std;const int inf=99999999;const int N=110;int f[N],a[N],cap[N][N],flow[N][N],p[N];using namespace std;int n;int F;int s,t;void EK_(){ queue q; memset(flow,0,sizeof(flow)); for(;;) { memset(a,0,sizeof(a)); q.push(s); a[s]=inf; while(!q.empty()) { int u=q.front(); q.pop(); for(int v=0;v<=n+1;v++) { if(!a[v]&&cap[u][v]>flow[u][v]&&flow[u][v]