P1344 [USACO4.4]追查坏牛奶Pollutant Control[最小割]

题目描述

你第一天接手三鹿牛奶公司就发生了一件倒霉的事情:公司不小心发送了一批有三聚氰胺的牛奶。很不幸,你发现这件事的时候,有三聚氰胺的牛奶已经进入了送货网。
这个送货网很大,而且关系复杂。你知道这批牛奶要发给哪个零售商,但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成,每辆卡车都在各自固定的两个仓库之间单向运输牛奶。

在追查这些有三聚氰胺的牛奶的时候,有必要保证它不被送到零售商手里,所以必须使某些运输卡车停止运输,但是停止每辆卡车都会有一定的经济损失。你的任务是,在保证坏牛奶不送到零售商的前提下,制定出停止卡车运输的方案,使损失最小。

输入输出格式

输入格式:

第一行: 两个整数N(2<=N<=32)、M(0<=M<=1000), N表示仓库的数目,M表示运输卡车的数量。仓库1代 表发货工厂,仓库N代表有三聚氰胺的牛奶要发往的零售商。 第2..M+1行: 每行3个整数Si,Ei,Ci。其中Si,Ei表示这 辆卡车的出发仓库,目的仓库。Ci(0 <= C i <= 2,000,000) 表示让这辆卡车停止运输的损失。

输出格式:

两个整数C、T:C表示最小的损失,T表示在损失最小的前提下,最少要停止的卡车数。
usaco的第二问:
接下来T行表示你要停止哪几条线路。如果有多种方案使损失最小,输出停止的线路最少的方案。如果仍然还有相同的方案,请选择开始输入顺序最小的。

输入输出样例

输入样例#1:

4 5
1 3 100
3 2 50
2 4 60
1 2 40
2 3 80

输出样例#1:

60 1
3

题解

第一问:求最大流(最小割最大流一样的)
然后把边权从大到小排序(因为要使停止的路线最少)
一条一条边去判断,如果删去该边之后,减小的最大流等于该边的边权(也就是损失),那么就删了这条边.
//删了之后记得减去
从x到y可以有很多条不同的路,所以在删边时不能直接赋成0,而是减掉这条边的边权。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/*
ID: ylx14271
PROG: milk6
LANG: C++
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int read()
{
char s;int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9'){k=k*10+(s-'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
int pre[100];
int n,m;
struct node
{
int u,v,w;//w:损失
int id;
} a[3000];
int f[50][50];//流量(损失
int c[50][50];
int p[100],a1;
int u1,v1,c1;
int q[4000];
void add(int uu,int vv,int ww)//连两条边,一条正的边和一条反向边
{
f[uu][vv]+=ww;//加到uu→vv这条边上去
a1++;
a[a1].id=a1;
a[a1].u=uu;a[a1].v=vv;a[a1].w=ww;//存起来
}
int w[4000],d1;
int cmp(node aa,node bb)
{
if (aa.w==bb.w) return aa.id<bb.id;
return aa.w>bb.w;
}
int spfa(int x)
{
memcpy(c,f,sizeof(c));//c存f数组的东西
c[a[x].u][a[x].v]-=a[x].w;//删掉这条边
int ans1=0;
while (true)//搜到 搜不到路径
{
int l=0,r=1;q[1]=1;
memset(pre,-1,sizeof(pre));//初始化
while (l<r)
{
l++;
int x1=q[l];
//cout<<x1<<" ";
for (int i=1;i<=n;i++)
{
if (c[x1][i]>0&&pre[i]==-1)//没被走过(没有前驱)并且流量<容量
{
pre[i]=x1;//标记
r++;q[r]=i;//入队
}
}
if (pre[n]>0) break;//搜完了
}
//cout<<endl;
if (pre[n]==-1) break; //找不到就退掉
int mi=233333333;
for (int i=n;i>1;i=pre[i]) mi=min(mi,c[pre[i]][i]);//找瓶颈
for (int i=n;i>1;i=pre[i]) c[pre[i]][i]-=mi;//减去
ans1+=mi;
//cout<<"--- "<<mi<<" \n";
}
return ans1;
}
int main()
{
freopen("milk6.in","r",stdin);
freopen("milk6.out","w",stdout);
n=read();
m=read();
a1=0;
for (int i=1;i<=m;i++)//建图
{
u1=read();v1=read();c1=read();
add(u1,v1,c1);
}
int xxx=spfa(0);//找最大流
printf("%d ",xxx);
d1=0;
int s1=0;
sort(a+1,a+m+1,cmp);
for (int j=1;j<=m;j++)//一条一条边的删
{
s1=spfa(j);
if (s1+a[j].w==xxx)
{
f[a[j].u][a[j].v]-=a[j].w;//开始没写这句然后炸了
d1++;//存起来
w[d1]=a[j].id;
xxx=s1;
}
}
printf("%d\n",d1);
sort(w+1,w+d1+1);//从小到大排序
for (int i=1;i<=d1;i++) printf("%d\n",w[i]);
return 0;
}