一看就知道是模板题= = ，不说什么了= =
PS：回去搞期末了，暑假再来刷题了
CODE：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define maxn 1010 7 #define maxm 20010 8 #define inf 0x7fffffff 9 using namespace std; 10 struct edges{ 11 int to,next,cap,dist;bool b; 12 }edge[maxm]; 13 int n,m,s,t,k,l; 14 int next[maxn],dist[maxn],way[maxn],h[maxn],p[maxn],gap[maxn]; 15 bool b[maxn]; 16 queue<int> q; 17 int addedge(int from,int to,int cap,int dist,bool bo){ 18 l++; 19 edge[l*2]=(edges){to,next[from],cap,dist,bo}; 20 edge[l*2+1]=(edges){from,next[to],0,-dist,bo}; 21 next[from]=l*2;next[to]=l*2+1; 22 return 0; 23 } 24 bool spfa(){ 25 memset(b,0,sizeof(b)); 26 for (int i=1;i<=n;i++) dist[i]=inf; 27 dist[1]=0; 28 q.push(1); 29 while (!q.empty()){ 30 int u=q.front();q.pop(); 31 b[u]=0; 32 for (int i=next[u];i;i=edge[i].next) 33 if (edge[i].cap&&dist[edge[i].to]>dist[u]+edge[i].dist) { 34 dist[edge[i].to]=dist[u]+edge[i].dist; 35 way[edge[i].to]=i; 36 if(!b[edge[i].to]){ 37 b[edge[i].to]=1; 38 q.push(edge[i].to); 39 } 40 } 41 } 42 if (dist[t]==inf) return 0; 43 return 1; 44 } 45 int mcmf(int cap){ 46 int cost=0; 47 while (spfa()){ 48 int x=n,flow=inf; 49 while (x!=1){ 50 flow=min(flow,edge[way[x]].cap); 51 x=edge[way[x]^1].to; 52 } 53 if (flow>=cap) return (cost+=dist[n]*cap); 54 cost+=dist[n]*flow; 55 cap-=flow; 56 x=n; 57 while(x!=1){ 58 edge[way[x]].cap-=flow; 59 edge[way[x]^1].cap+=flow; 60 x=edge[way[x]^1].to; 61 } 62 } 63 return cost; 64 } 65 int sap(int u,int flow){ 66 if (u==t) return flow; 67 int cur=0; 68 for (int i=p[u];i;i=edge[i].next) 69 if (edge[i].b&&edge[i].cap&&h[u]==h[edge[i].to]+1){ 70 int cut=sap(edge[i].to,min(flow-cur,edge[i].cap)); 71 edge[i].cap-=cut;edge[i^1].cap+=cut; 72 p[u]=i; 73 if ((cur+=cut)==flow ) return flow; 74 } 75 if (!(--gap[h[u]])) h[s]=n; 76 gap[++h[u]]++; 77 p[u]=next[u]; 78 return cur; 79 } 80 int maxflow(){ 81 memset(gap,0,sizeof(gap)); 82 memset(h,0,sizeof(h)); 83 gap[0]=n; 84 for(int i=1;i<=n;i++) p[i]=next[i]; 85 int flow=0; 86 while (h[s]<n) flow+=sap(s,inf); 87 return flow; 88 } 89 int main(){ 90 scanf("%d%d%d",&n,&m,&k); 91 s=1,t=n; 92 for (int i=1;i<=m;i++) { 93 int x,y,cap,d; 94 scanf("%d%d%d%d",&x,&y,&cap,&d); 95 addedge(x,y,cap,0,1); 96 addedge(x,y,inf,d,0); 97 } 98 int ans=maxflow(); 99 printf("%d %d ",ans,mcmf(k)); 100 return 0; 101 }
|
|
|