首页 > > 程序设计 > C/C++ >

bzoj2324 [ ZJOI2011 ] -- 费用流

2018-06-17 23:07:00来源：未知阅读 ()

先用floyd求出不经过大于i或大于j的点的i,j间最短路径，然后考虑这样建图：

对于每个点i，将其拆分成i、i'，连边：

s -> i' 容量为INF，费用为0

s -> 1 容量为k，费用为0

i' -> j 容量为1，费用为dist[i][j]

i -> t 容量为1，费用为0

此时这张图的最小费用最大流就是答案。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define N 400
 6 #define M 20010
 7 #define INF 2147483647
 8 struct Edge{
 9     int c,w,f,t,nx;
10 }e[M<<1],e1[M<<1];
11 int i,j,k,x,y,z,n,m,h[N],H[N],d[N],s,di[N][N],p[N],q[M],Min[N],a[N],l,r,t,Num=1,Ans,K;
12 bool b[N];
13 inline int _Min(int x,int y){return x<y?x:y;}
14 inline void Add(int x,int y,int c,int w){
15     e[++Num].t=y;e[Num].f=x;e[Num].c=c;e[Num].w=w;e[Num].nx=h[x];h[x]=Num;
16     e[++Num].t=x;e[Num].f=y;e[Num].c=0;e[Num].w=-w;e[Num].nx=h[y];h[y]=Num;
17 }
18 inline bool Spfa(){
19     memset(b,0,sizeof(b));
20     memset(d,127,sizeof(d));
21     l=0;q[r=1]=s;d[s]=0;Min[s]=INF;
22     while(l<r){
23         int x=q[++l];
24         b[x]=0;
25         for(int i=h[x];i;i=e[i].nx)
26         if(e[i].c>0&&d[e[i].t]>d[x]+e[i].w){
27             d[e[i].t]=d[x]+e[i].w;
28             p[e[i].t]=i;
29             Min[e[i].t]=_Min(Min[x],e[i].c);
30             if(!b[e[i].t]){
31                 b[e[i].t]=1,q[++r]=e[i].t;
32             }
33         }
34     }
35     if(d[t]>2000000000)return 0;
36     Ans+=d[t]*Min[t];
37     for(int i=p[t];i;i=p[e[i].f])e[i].c-=Min[t],e[i^1].c+=Min[t];
38     return 1;
39 }
40 int main()
41 {
42     scanf("%d%d%d",&n,&m,&K);t=((++n)<<1)|1;
43     memset(di,63,sizeof(di));
44     for(i=1;i<=m;i++){
45         scanf("%d%d%d",&x,&y,&z);
46         if(z<di[++x][++y])di[x][y]=di[y][x]=z;
47     }
48     Add(s,1,K,0);
49     for(i=2;i<=n;i++)Add(i,t,1,0),Add(s,i+n,1,0);
50     for(k=1;k<=n;k++)
51     for(i=1;i<=n;i++)
52     for(j=1;j<=n;j++)
53     if(i!=j){
54         if(di[i][k]+di[k][j]<di[i][j])di[i][j]=di[i][k]+di[k][j];
55         if(k==j&&j>i&&di[i][j]<1000000000)Add(i==1?1:n+i,j,INF,di[i][j]);
56     }
57     n=t;
58     while(Spfa());
59     printf("%d",Ans);
60     return 0;
61 }