终于开始网络流了。EK算法很好懂。
这道题可以设一个超级源点指向所有普通源点，一个超级汇点被所有汇点指向，然后计算最大流就是答案要求的最大电力。
读入太麻烦了可以用cin。不过…其实用输入外挂的话又快又省事。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define eps 1e-6 #define INF 0x3f3f3f3f #define PI acos(-1.0) //#define ll __int64 #define ll long long #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 #define M 1000000007 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; int n,m,np,nc; int p[200],flow[200][200],a[200],cap[200][200]; int s,t; //超级源点和超级汇点 inline int ReadInt() { char ch = getchar(); int data = 0; while (ch < '0' || ch > '9') { ch = getchar(); } do { data = data*10 + ch-'0'; ch = getchar(); }while (ch >= '0' && ch <= '9'); return data; } int ek() { queue q; memset(flow,0,sizeof(flow)); int f=0; for(;;) { memset(a,0,sizeof(a)); a[s]=INF; q.push(s); 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]) { p[v]=u; q.push(v); a[v]=min(a[u],cap[u][v]-flow[u][v]); } } } if(a[t]==0) break; for(int u=t;u!=s;u=p[u]) { flow[p[u]][u]+=a[t]; flow[u][p[u]]-=a[t]; } f+=a[t]; } return f; } int main() { int x,y,z; char e; while(~scanf("%d%d%d%d",&n,&np,&nc,&m)) { memset(cap,0,sizeof(cap)); t=s=n;t++; for(int i=1;i<=m;i++) { x=ReadInt(); y=ReadInt(); z=ReadInt();; cap[x][y]=z; } for(int i=1;i<=np;i++) { x=ReadInt(); y=ReadInt(); cap[s][x]=y; //超级源点连向所有普通源点 } for(int i=1;i<=nc;i++) { cin>>e>>x>>e>>y; //所有普通汇点连向超级汇点 cap[x][t]=y; } printf("%d\n",ek()); } return 0; }