hdu 6201(最小费用最大流)

transaction transaction transaction

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)
Total Submission(s): 1003 Accepted Submission(s): 488
Problem Description
Source
2017 ACM/ICPC Asia Regional Shenyang Online
直接构图费用流跑一遍
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cstdlib>
  6 #include<string.h>
  7 #include<set>
  8 #include<vector>
  9 #include<queue>
 10 #include<stack>
 11 #include<map>
 12 #include<cmath>
 13 typedef long long ll;
 14 typedef unsigned long long LL;
 15 using namespace std;
 16 const double PI=acos(-1.0);
 17 const double eps=0.0000000001;
 18 const int INF=0x3f3f3f3f;
 19 const int N=1000000+100;
 20 int a[N];
 21 int head[N];
 22 int dis[N];
 23 int pre[N];
 24 int vis[N];
 25 int tot;
 26 int m,n;
 27 struct node{
 28     int from,to,next,flow,cost;
 29 }edge[N<<1];
 30 void init(){
 31     memset(head,-1,sizeof(head));
 32     tot=0;
 33 }
 34 void add(int u,int v,int c,int cost){
 35     edge[tot].from=u;
 36     edge[tot].to=v;
 37     edge[tot].flow=c;
 38     edge[tot].cost=cost;
 39     edge[tot].next=head[u];
 40     head[u]=tot++;
 41     edge[tot].from=v;
 42     edge[tot].to=u;
 43     edge[tot].flow=0;
 44     edge[tot].cost=-cost;
 45     edge[tot].next=head[v];
 46     head[v]=tot++;
 47 }
 48 int spfa(int s,int t){
 49     memset(pre,-1,sizeof(pre));
 50     memset(dis,INF,sizeof(dis));
 51     memset(vis,0,sizeof(vis));
 52     queue<int>q;
 53     dis[s]=0;
 54     vis[s]=1;
 55     q.push(s);
 56     while(!q.empty()){
 57         int x=q.front();
 58         q.pop();
 59         vis[x]=0;
 60         for(int i=head[x];i!=-1;i=edge[i].next){
 61             int v=edge[i].to;
 62             if(edge[i].flow&&dis[v]>dis[x]+edge[i].cost){
 63                 dis[v]=edge[i].cost+dis[x];
 64                 pre[v]=i;
 65                 if(vis[v]==0){
 66                     vis[v]=1;
 67                     q.push(v);
 68                 }
 69 
 70             }
 71         }
 72     }
 73     if(pre[t]==-1)return 0;
 74     return 1;
 75 }
 76 int MCMF(int s,int t){
 77     int flow=0;
 78     int cost=0;
 79     while(spfa(s,t)){
 80         int minn=INF;
 81         for(int i=pre[t];i!=-1;i=pre[edge[i].from]){
 82             minn=min(minn,edge[i].flow);
 83         }
 84         for(int i=pre[t];i!=-1;i=pre[edge[i].from]){
 85             edge[i].flow=edge[i].flow-minn;
 86             edge[i^1].flow=edge[i^1].flow+minn;
 87             cost=edge[i].cost+cost;
 88            // cout<<cost<<endl;
 89         }
 90         flow=flow+minn;
 91     }
 92     return cost;
 93 }
 94 int main(){
 95     int tt;
 96     scanf("%d",&tt);
 97     while(tt--){
 98         init();
 99         scanf("%d",&n);
100         for(int i=1;i<=n;i++){
101             scanf("%d",&a[i]);
102         }
103         int s=0;
104         int s1=n+1;
105         int t=n+2;
106         add(s,s1,1,0);
107         for(int i=1;i<=n;i++){
108             add(s1,i,1,-a[i]);
109         }
110         for(int i=1;i<=n;i++){
111             add(i,t,1,a[i]);
112         }
113         for(int i=1;i<=n-1;i++){
114             int u,v,cost;
115             scanf("%d%d%d",&u,&v,&cost);
116             add(u,v,1,cost);
117             add(v,u,1,cost);
118         }
119         cout<<abs(MCMF(s,t))<<endl;
120     }
121 }