ACM_Someone like you

  1 做得還算麻利~
  2 /*最大閉合子圖
  3 題意：建通訊站。每個通訊站有一定耗費，兩個特定的通訊站之間建立通訊以后
  4 會有一定收益，問怎樣建立通訊站可以使得收益最大 。
  5 ——最大權閉合子圖->最小割
  6 ——url：http://acm.hdu.edu.cn/showproblem.php?pid=3879
  7 思路：
  8 首先考慮將圖轉化。
  9 即一條通訊線路有一定收益wi（即為正點權），但需要建立兩個通訊站，
 10 這兩個通訊站有一定造價pi(即為負點權)。
 11 將通訊線路也變成點，點權為收益，連兩條有向只向兩個通訊站。
 12 原來的通訊站點權不變。則start=0;end=m+n+1;totals=end+1;
 13 由此，題目轉化為在新的圖中求一個閉合圖，使得其點權最大，即最大權閉合子圖
 14 具體見圖如下：
 15 建一個源點Start，與每個通訊線路的點相連，邊權為收益
 16 建一個匯點end，end與每個通訊站相連，邊權為建造費用
 17 通訊站與通訊線路之間的邊權為無窮大
 18 最后的結果為所有通訊線路總的收益-最小割(最大流)
 19 */ 
 20 #include <iostream>
 21 #include<cstdio>
 22 #include<cstring>
 23 #include<vector>
 24 #include<queue>
 25 #include<algorithm>
 26 using namespace std;
 27 #define min(a,b) ((a)<(b))?(a):(b)
 28 #define max(a,b) ((a)>(b))?(a):(b)
 29 #define MAXN  60000//這里取略大于m+n+2的值（500+50000+2）所以這里取60000否則會runtime error 
 30 #define MAXM 5400000//M取N的平方倍或者N*9
 31 #define INF 0x3f3f3f3f
 32 
 33 struct node
 34 {
 35     int n;//點編號
 36     int w;//點權
 37 }Node[MAXN];
 38 //鏈式前向星
 39 struct enode
 40 {
 41     int t;
 42     int w;                //權值
 43     int c;                //流量
 44 //  int cost;
 45 //    int pre;            //前向指針
 46     int next;
 47 };
 48 
 49 
 50     struct enode e[MAXM];
 51     int box[MAXN],ecnt;
 52     //int etail[MAXN];        //尾部
 53     void init()
 54     {
 55         ecnt=0;
 56         memset(box,-1,sizeof(box));
 57     //    memset(etail,-1,sizeof(etail));        //初始化尾部
 58     }
 59     void addedge(int f,int t,int c)            //流量重載
 60     {
 61         e[ecnt].next=box[f];
 62         e[ecnt].t=t;
 63         e[ecnt].c=c;
 64         box[f]=ecnt++;
 65         e[ecnt].next=box[t];
 66         e[ecnt].t=f;
 67         e[ecnt].c=0;
 68         box[t]=ecnt++;
 69     }
 70 int sap(int s,int t,int N)//最大流問題
 71 {
 72     int gap[MAXN],lvl[MAXN],cur[MAXN],pre[MAXN];
 73     int curflow,ans=0,u,tmp,neck,i;
 74     memset(lvl,0,sizeof(lvl));
 75     memset(gap,0,sizeof(gap));
 76     memset(pre,-1,sizeof(pre));
 77     for(i=0;i<N;i++)
 78         cur[i]=box[i];
 79     gap[0]=N;
 80     u=s;
 81     while(lvl[s]<N)
 82     {
 83         if(u==t)
 84         {
 85             curflow=INF;
 86             for(i=s;i!=t;i=e[cur[i]].t)
 87             {
 88                 if(curflow>e[cur[i]].c)
 89                 {
 90                     neck=i;
 91                     curflow=e[cur[i]].c;
 92                 }
 93             }
 94             for(i=s;i!=t;i=e[cur[i]].t)
 95             {
 96                 tmp=cur[i];
 97                 e[tmp].c-=curflow;
 98                 e[tmp^1].c+=curflow;
 99             }
100             ans+=curflow;
101             u=neck;
102         }
103         for(i=cur[u];i!=-1;i=e[i].next)
104             if(e[i].c && lvl[u]==lvl[e[i].t]+1)
105                 break;
106         if(i!=-1)
107         {
108             cur[u]=i;
109             pre[e[i].t]=u;
110             u=e[i].t;
111         }
112         else
113         {
114             if(--gap[lvl[u]]==0)
115                 break;
116              cur[u]=box[u];
117             for(tmp=N,i=box[u];i!=-1;i=e[i].next)
118                 if(e[i].c)
119                     tmp=min(tmp,lvl[e[i].t]);
120             lvl[u]=tmp+1;
121             gap[lvl[u]]++;
122             if(u!=s)
123                 u=pre[u];
124         }
125     }
126     return ans;
127 }
128 int main()
129 {
130      int m,n,a,b,c,t,w;
131      int i,j,k;
132      int start,end,ans;
133   while(scanf("%d%d",&n,&m)!=EOF)  //;
134    {
135         //scanf("%d%d",&n,&m);
136         start=ans=0;
137         end=n+m+1;
138         init();
139         for(i=1;i<=n;i++)
140         {
141             scanf("%d",&w);
142             addedge(i+m,end,w);//終點和負點權邊相連
143 
144         }
145         for(i=1;i<=m;i++)
146         {
147             scanf("%d%d%d",&a,&b,&c);//正點權
148             ans+=c;
149             addedge(i,b+m,INF);//建圖關鍵
150             addedge(i,a+m,INF);//建圖關鍵
151             addedge(start,i,c);
152         }
153         t=sap( start,end,end+1);//*/
154         printf("%d\n",ans-t);
155    }
156     return 0;
157 }
158 /*
159 Sample Input
160 
161 5 5
162 1 2 3 4 5
163 1 2 3
164 2 3 4
165 1 3 3
166 1 4 2
167 4 5 3
168 
169 Sample Output
170 
171 2
172 */