题意： n个点，其中np个点最多能发p[i]电,nc个点最多消耗c[i]电,有m条传输路线，最多能传输w[i]电，问最多总共能消耗多少电。
解题思路： 网络流经典题。 没学网络流前想了下枚举边不就做出来了嘛，但是仔细一想，发现如果随意枚举的话，会出现某些发电的点不能被充分利用的情况，如果调换下顺序，则能得到充分利用，所以感觉需要解决的就是一个顺序问题。 然后学了Edmonds-Karp 算法后，发现ek算法其实就是加了回边，每次去走回边其实相当于撤销了原来被走过的正边，然后这样每次bfs都这样去走，直到走不到汇点为止，就能保证正确性了。
感觉这个算法巧的地方就在于走回边了。
这个题dfs的话会t，改成bfs就过。
代码： #include #include #include #include #define ps push_back using namespace std; const int maxn=120; const int inf=1e9; struct node{ int from; int cap; int x; }que[maxn*maxn]; int a[maxn][maxn]; int n, m, np, cp, s, t; int used[maxn]; /* int dfs(int u, int t, int cap) { if(u==t)return cap; int res; used[u]=1; for(int i=0; i<=t; i++) { if(used[i]==0 && a[u][i]>0) { res=dfs(i, t, min(cap, a[u][i])); if(res>0) { a[u][i]-=res; a[i][u]+=res; return res; } } } return 0; } */ int bfs(int s, int t) { int head, tail, x; head=tail=0; que[tail].from=-1, que[tail].x=s, que[tail++].cap=inf; used[s]=1; while(head0) { used[i]=1; que[tail].from=head, que[tail].x=i, que[tail++].cap=min(que[head].cap, a[x][i]); } } head++; } if(x==t) { int mi=que[head].cap; while(que[head].from!=-1) { a[que[que[head].from].x][que[head].x]-=mi; a[que[head].x][que[que[head].from].x]+=mi; head=que[head].from; } return mi; } return 0; } int f(int s, int t) { int flow=0; while(1) { memset(used, 0, sizeof used); int res=bfs(s, t); if(res==0)return flow; flow+=res; } } int main() { ios::sync_with_stdio(false); cin.tie(0); string in; stringstream ss; char e; while(cin>>n>>np>>cp>>m) { memset(a, 0, sizeof a); int u, v, w; s=n, t=n+1; while(m--) { cin>>e>>u>>e>>v>>e>>w; a[u][v]=w; } while(np--) { cin>>e>>v>>e>>w; a[s][v]=w; } while(cp--) { cin>>e>>v>>e>>w; a[v][t]=w; } cout<