（同時也是HDU 2982，UVA的資料多）
題意：平面上有m條有向線段連接配接了n個點。你從某個點出發順着有向線段行走，給走過的每條線段塗一種不同的顔色，最後回到起點。你可以多次行走，給多個回路塗色（要麼不塗色，要麼就至少給一個回路上的邊全部塗色）。可以重複經過一個點，但不能重複經過一條有向線段。如下圖所示的是一種塗色方法（虛線表示未塗色，即每次都可以從任意點出發染色）。每塗一個機關長度将得到X分，但每使用一種顔色将扣掉Y分。假設你擁有無限多種的顔色，問如何塗色才能使得分最大？輸入保證若存在有向線段u -> v，則不會出現有向線段v -> u。
n <= 100，m <= 500，1 <= X，Y <= 1000。
對于坐标（x，y）0 <= x，y <= 1000。
思路：看劉汝佳的書的第二種方法，再參考這篇博文才把代碼長度降下來了。http://blog.csdn.net/u013368721/article/details/30553815
要求的就是最大費用循環流（即每找到一個環就可以進行增廣）。找環可能并不複雜，但是要找一個最大的環就有點複雜了，是以用網絡流解決。又因為找的是最大費用，按老套路的話會出現無限增大費用的情況，是以要先将每條邊的費用取相反數（前面加個負），才可以有機會求最小費用流。而這些邊的權有正有負，取完之後也可能出現負環了，是以主要問題就是解決負環。
用最小費用流求最大費用循環流時，解決負環的一種方法：
（1）先将所有邊權取反。
（2）建邊。正權值的邊容量為1，費用為權值。負權值的邊u->v拆成3條邊，分别是S->v，v->u，u->T，容量都為1，v->u費用為負權的相反數，其他2條費用為0。這樣會出現某個點有多條邊連到S或T，可以互相抵消到一方為0為止，統計剩下多少條k，将其中1條的容量設為k，其他的全部删掉。如果全部抵消掉了，那就将連S和T的邊全部删掉。（這個删邊的方法有技巧）
（3）跑一次最小費用流得到的總費用，加上所有負權之和之後（注：此時答案已為負的），再取反即得到最大費用。
删邊技巧是，在建這S->v，v->u，u->T 三條邊時，先建中間那條，統計該點連到S幾次，減去連到T點幾次，結果若為正，則與S連一條邊，容量就是幾次，若負，同理。
至于why it works！得好好想想~
畫幾個點驗證了一下發現，如果一個原圖中的環（權值大于0）值得取，那麼流會自動流向該環原圖中的負權邊。而如果不值得取，那麼會流向原圖中的正權邊。因為我們是用sum（負值）加上那個費用（正值），是以當該環要取時，則自動減去那些負權，不取呢，會自動減去那些正權（而那些負權的完全沒取到）。不懂就畫個環出來驗證吧。
1 #include <bits/stdc++.h>
2 #define LL long long
3 #define pii pair<int,int>
4 #define pdi pair<double,int>
5 #define INF 0x7f7f7f7f
6 using namespace std;
7 const int N=200;
8 int x[N], y[N], rudu[N];
9 int earn, lost, n;
10 vector<int> vect[N], vec[N];
11 double sum;
12
13 struct node
14 {
15 int from, to, cap, flow;
16 double val;
17 node(){};
18 node(int from,int to,double val,int cap,int flow):from(from),to(to),val(val),cap(cap),flow(flow){};
19 }edge[90000];
20 int edge_cnt;
21
22 void add_node(int from,int to,double val,int cap,int flow)
23 {
24 edge[edge_cnt]=node(from, to, val, cap, flow );
25 vec[from].push_back(edge_cnt++);
26 }
27
28 void build_graph()
29 {
30 for(int i=1; i<=n; i++)
31 {
32 for(int j=0; j<vect[i].size(); j++)
33 {
34 int t=vect[i][j];
35 double v= lost - sqrt( pow(x[i]-x[t],2)+pow(y[i]-y[t],2) )*earn;
36
37 if(v<0)
38 {
39 add_node(t, i, -v, 1, 0 ); //反邊
40 add_node(i, t, v, 0, 0 );
41 sum+=v;
42 rudu[t]++,rudu[i]--;
43 }
44 else
45 {
46 add_node(i, t, v, 1, 0);
47 add_node(t, i, -v, 0, 0);
48 }
49 }
50 }
51 for(int i=1; i<=n; i++)
52 {
53 if(rudu[i]>0)
54 {
55 add_node(0, i, 0, rudu[i], 0);
56 add_node(i, 0, 0, 0, 0);
57 }
58 if(rudu[i]<0)
59 {
60 add_node(i, n+1, 0, -rudu[i], 0);
61 add_node(n+1, i, 0, 0, 0);
62 }
63 }
64 }
65
66 int flow[N], path[N], inq[N];
67 double cost[N];
68
69 double spfa(int s,int e)
70 {
71 deque<int> que(1,s);
72 cost[s]=0;
73 flow[s]=INF;
74 inq[s]=1;
75 while(!que.empty())
76 {
77 int x=que.front();
78 que.pop_front();
79 inq[x]=0;
80 for(int i=0; i<vec[x].size(); i++)
81 {
82 node e=edge[vec[x][i]];
83 if(e.cap>e.flow && cost[e.to]>cost[e.from]+e.val )
84 {
85 flow[e.to]=min(flow[e.from],e.cap-e.flow);
86 cost[e.to]=cost[e.from]+e.val;
87 path[e.to]=vec[x][i];
88 if(!inq[e.to])
89 {
90 inq[e.to]=1;
91 que.push_back(e.to);
92 }
93 }
94 }
95 }
96 return cost[e];
97 }
98
99 double mcmf(int s,int e)
100 {
101 double ans_cost=0.0;
102 while(true)
103 {
104 memset(flow,0,sizeof(flow));
105 memset(inq,0,sizeof(inq));
106 memset(path,0,sizeof(path));
107 for(int i=0; i<=e; i++) cost[i]=1e39;
108
109 double tmp=spfa(s,e); //傳回費用
110 if(tmp>1e38) return ans_cost;
111 ans_cost+=tmp;
112
113 int ed=e;
114 while(ed!=s)
115 {
116 int t=path[ed];
117 edge[t].flow+=flow[n+1];
118 edge[t^1].flow-=flow[n+1];
119 ed=edge[t].from;
120 }
121 }
122 }
123
124 int main()
125 {
126 freopen("input.txt", "r", stdin);
127 int b, j=0;
128 while(scanf("%d", &n), n)
129 {
130 scanf("%d%d",&earn,&lost);
131 for(int i=0; i<=n+1; i++) vect[i].clear();
132 for(int i=0; i<=n+1; i++) vec[i].clear();
133 memset(edge,0,sizeof(edge));
134 memset(rudu,0,sizeof(rudu));
135 edge_cnt=0;
136 sum=0;
137
138 for(int i=1; i<=n; i++)
139 {
140 scanf("%d%d",&x[i],&y[i]);
141 while(scanf("%d",&b), b) vect[i].push_back(b); //原圖鄰接表
142 }
143 build_graph();
144 printf("Case %d: %.2f\n", ++j, -(mcmf(0,n+1)+sum)+0.0000001 );
145 }
146 return 0;
147 } AC代碼