UVa12092 Paint the Roads（最小费用最大流）

题目大概说一个n个点m条带权有向边的图，要给边染色，染色的边形成若干个回路且每个点都恰好属于其中k个回路。问最少要染多少边权和的路。

一个回路里面各个点的入度=出度=1，那么可以猜想知道各个点如果都恰好属于k个回路那么各个点的入度=出度=k。

这样就考虑用最小费用最大流了：

所有点u拆成两点u和u'，分别代表出度和入度;
原点向u连容量k费用0的边，u'向汇点连容量k费用0的边;
所有有向边<u,v>，u向v'连容量1费用边权的边。
这样跑最小费用最大流，如果最大流等于n*k，也就是说各个点的出度=入度=k，那么就有解，最小费用就是最小的解。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<algorithm>
 5 using namespace std;
 6 #define INF (1<<30)
 7 #define MAXN 111
 8 #define MAXM 5555
 9 
10 struct Edge{
11     int v,cap,cost,next;
12 }edge[MAXM];
13 int vs,vt,NV,NE,head[MAXN];
14 void addEdge(int u,int v,int cap,int cost){
15     edge[NE].v=v; edge[NE].cap=cap; edge[NE].cost=cost;
16     edge[NE].next=head[u]; head[u]=NE++;
17     edge[NE].v=u; edge[NE].cap=0; edge[NE].cost=-cost;
18     edge[NE].next=head[v]; head[v]=NE++;
19 }
20 
21 bool inque[MAXN];
22 int d[MAXN],pre[MAXN];
23 bool SPFA(){
24     for(int i=0; i<NV; ++i){
25         d[i]=INF; inque[i]=0;
26     }
27     d[vs]=0; inque[vs]=1;
28     queue<int> que;
29     que.push(vs);
30     while(!que.empty()){
31         int u=que.front(); que.pop();
32         for(int i=head[u]; i!=-1; i=edge[i].next){
33             int v=edge[i].v;
34             if(edge[i].cap && d[v]>d[u]+edge[i].cost){
35                 d[v]=d[u]+edge[i].cost;
36                 pre[v]=i;
37                 if(!inque[v]){
38                     inque[v]=1;
39                     que.push(v);
40                 }
41             }
42         }
43         inque[u]=0;
44     }
45     return d[vt]!=INF;
46 }
47 int mxflow;
48 int MCMF(){
49     int res=0;
50     while(SPFA()){
51         int flow=INF,cost=0;
52         for(int u=vt; u!=vs; u=edge[pre[u]^1].v){
53             flow=min(flow,edge[pre[u]].cap);
54         }
55         mxflow+=flow;
56         for(int u=vt; u!=vs; u=edge[pre[u]^1].v){
57             edge[pre[u]].cap-=flow;
58             edge[pre[u]^1].cap+=flow;
59             cost+=edge[pre[u]].cost;
60         }
61         res+=cost*flow;
62     }
63     return res;
64 }
65 
66 int main(){
67     int t,n,m,k;
68     scanf("%d",&t);
69     while(t--){
70         scanf("%d%d%d",&n,&m,&k);
71         vs=2*n; vt=vs+1; NV=vt+1; NE=0;
72         memset(head,-1,sizeof(head));
73         for(int i=0; i<n; ++i){
74             addEdge(vs,i,k,0);
75             addEdge(i+n,vt,k,0);
76         }
77         int a,b,c;
78         while(m--){
79             scanf("%d%d%d",&a,&b,&c);
80             addEdge(a,b+n,1,c);
81         }
82         mxflow=0;
83         int res=MCMF();
84         if(mxflow!=n*k) puts("-1");
85         else printf("%d
",res);
86     }
87     return 0;
88 }