POJ 1459 Power Network(ISAP 裸最大流)
题目链接:http://poj.org/problem?id=1459
注意输入格式就行,还是ISAP
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> const int N = 210; const int maxn = 300; const int maxm = 40000; #define MIN INT_MIN #define MAX INT_MAX #define LL long long using namespace std; int max(int a,int b){if(a>b)return a; else return b;} int min(int a,int b){if(a<b)return a; else return b;} int n,m; int head[maxn], sum, bnum; int dis[maxn]; int num[maxn]; int cur[maxn]; int pre[maxn]; struct node { int v, cap; int next; }edge[maxm]; void add(int u, int v, int cap) { edge[bnum].v=v; edge[bnum].cap=cap; edge[bnum].next=head[u]; head[u]=bnum++; edge[bnum].v=u; edge[bnum].cap=0; edge[bnum].next=head[v]; head[v]=bnum++; } void BFS(int source,int sink) { queue<int>q; while(q.empty()==false) q.pop(); memset(num,0,sizeof(num)); memset(dis,-1,sizeof(dis)); q.push(sink); dis[sink]=0; num[0]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=edge[i].next) { int v = edge[i].v; if(dis[v] == -1) { dis[v] = dis[u] + 1; num[dis[v]]++; q.push(v); } } } } int ISAP(int source,int sink,int n) { memcpy(cur,head,sizeof(cur)); int flow=0, u = pre[source] = source; BFS( source,sink); while( dis[source] < n ) { if(u == sink) { int df = MAX, pos; for(int i = source;i != sink;i = edge[cur[i]].v) { if(df > edge[cur[i]].cap) { df = edge[cur[i]].cap; pos = i; } } for(int i = source;i != sink;i = edge[cur[i]].v) { edge[cur[i]].cap -= df; edge[cur[i]^1].cap += df; } flow += df; u = pos; } int st; for(st = cur[u];st != -1;st = edge[st].next) { if(dis[edge[st].v] + 1 == dis[u] && edge[st].cap) { break; } } if(st != -1) { cur[u] = st; pre[edge[st].v] = u; u = edge[st].v; } else { if( (--num[dis[u]])==0 ) break; int mind = n; for(int id = head[u];id != -1;id = edge[id].next) { if(mind > dis[edge[id].v] && edge[id].cap != 0) { cur[u] = id; mind = dis[edge[id].v]; } } dis[u] = mind+1; num[dis[u]]++; if(u!=source) u = pre[u]; } } return flow; } void initt() { memset(head,-1,sizeof(head)); bnum=0; } int main() { int np,nc,u,v,w; while(scanf("%d%d%d%d",&n,&np,&nc,&m) != EOF) { initt(); for(int i = 0;i<m;i++) { scanf(" (%d,%d)%d",&u,&v,&w); add(u+1,v+1,w); } for(int i = 0;i<np;i++) { scanf(" (%d)%d",&v,&w); add(0,v+1,w); } for(int i = 0;i<nc;i++) { scanf(" (%d)%d",&u,&w); add(u+1,n+1,w); } int ans = ISAP(0,n+1,n+2); cout<<ans<<endl; } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。