你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。
{批注：先前不知是哪个写了一个要不得的翻译，这才是正常的翻译，读起来也觉得比较健康——Cow-Tsc} {修改下，更现实——pyh119}
格式
PROGRAM NAME: milk6
INPUT FORMAT:(file milk6.in)
第一行: 两个整数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) 表示让这辆卡车停止运输的损失。
OUTPUT FORMAT:(file milk6.out)
第1行两个整数c、t,c表示最小的损失，T表示要停止的最少卡车数。接下来t 行表示你要停止哪几条线路。如果有多种方案使损失最小，输出停止的线路最少的方案。如果仍然还有相同的方案，请选择开始输入顺序最小的。
SAMPLE INPUT
4 5
1 3 100
3 2 50
2 4 60
1 2 40
2 3 80
SAMPLE OUTPUT
60 1
3
分析：
要用到最小割最大流定理。
首先求出最大流，那么最小割的容量就是最大流的流量。然后找有没有容量=最小割容量的“桥”（这里的桥就是去掉这条边后，由源点出发无法到达汇点），如果有那么这个桥就是答案。然后对每条容量不大于最小割的边，去掉后求一次最大流（估计这里我的算法太麻烦了）。如果流量的减少量=这条边的容量，那么这条边一定属于最小割。找出这样所有的边后，如果这些边的容量和=最小割容量，那么符合题目条件的最小割已求出。剩下的工作就是搜索了。我用的是枚举每一条满足上述的边。
对于*1001+1的解释：orz P〇〇н
对于一个网络，已知它的弧的数量不超过1000，那么经过一定的技术处理，直接用基本的网络流算法就能实现了。
在读入每条弧c[i,j]时，将其容量c[i,j]乘以1001加1存到f[i,j]中，即f[i,j]=c[i,j]*1001+1(这里不考虑两条弧连接相同两个结点的情况)，然后就用朴素的方法在f上求最大流得到maxflow。那么真实的最大流就是maxflow div 1001，元素最少最小割的元素个数就是maxflow mod 1001。为什么呢？我试试看能不能稍微讲清楚一点：
首先，为什么maxflow div 1001就是原最大流呢？回想一下，每次我们求到一条增广轨后，进行track_back操作时，必然会由已求得的路径上的某条弧的容量，确定这个可行流的流量flow，假设这条弧为<i,j>。那么这条可行流的流量flow1=f[i1,j1]=c[i1,j1]*1001+1。依此类推，会得到flow2=f[i2,j2]=c[i2,j2]*1001+1、flow3=f[i3,j3]=c[i3,j3]*1001+1……最后找到了k条增广轨，得到的最大流maxflow=flow1+flow2+flow3……+flowk=(c[i1,j1]+c[i2,j2]+c[i3,c3]+……+c[ik,jk])*1001+1*k。 （其实，这段叙述很不准确，因为f[i,j]的值在前面找增广轨的过程中，有可能改变，这里只能算是孤立起来辅助理解吧）
显然，k<=1000，当取maxflow div 1001时，得到的就是最大流，因为k在div过程中必然被忽略
另一方面，每找到一条增广轨，必然比原有流量*1001多加上一个1（因为flow=f[i,j]=c[i,j]*1001+1，但回过头看看第一行红字，如果两条弧连接了相同两个结点，这里多加的就不是一个1，而是两个1了）。对于每个多加上的1，都是由一条增广轨的某条弧决定的，只要删除这条弧后，这个流就不通了。于是，maxflow mod 1001就是需要删的弧的个数。
那么为什么这样求到的割集元素最少呢？因为，如果原图存在一个最大流量相等，但割集元素多一个 的情况时，那么在新图中，如果多找了一次增广轨，那么就多加了一个1，会超出已知最大流上限了（不能理解？尽量想象一下嘛，感觉是这样），这样的最大流是求不出来的。求到的自然而然的就是最少的那一个了。
【参考程序】：
/*
ID: XIONGNA1
PROG: milk6
LANG: C++
*/
#include<iostream>
#include<cstring>
using namespace std;
struct node
{
int x,y;
long long f;
} e[1001];
long long c[40][40],c2[40][40];
int queue[40],ans[1001],pre[40];
bool vis[40];
int n,m;
long long maxf;
long long getmax()
{
int head,tail,now,p; long long ss=0,flow;
while (true)
{
for (int i=1;i<=n;i++)
{
vis[i]=false; pre[i]=0;
}
queue[1]=1; vis[1]=true;
head=tail=1;
while (head<=tail)
{//bfs find flow
now=queue[head];
for (int i=1;i<=n;i++)
if (!vis[i] && c2[now][i]>0)
{
vis[i]=true;
tail++;
queue[tail]=i; pre[i]=now;
}
head++;
}
if (!vis[n]) break;
flow=0x7FFFFFFF;
p=n;
while (p!=1)//change flow
{
if (flow>c2[pre[p]][p]) flow=c2[pre[p]][p];
p=pre[p];
}
ss+=flow;
p=n;
while (p!=1)
{
c2[pre[p]][p]-=flow;
c2[p][pre[p]]+=flow;
p=pre[p];
}
}
return ss;
}
int main()
{
freopen("milk6.in","r",stdin);
freopen("milk6.out","w",stdout);
scanf("%d%d",&n,&m);
memset(c,0,sizeof(c));
int s;
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&e[i].x,&e[i].y,&s);
e[i].f=(long long)s*1001+1;
c[e[i].x][e[i].y]+=(long long)s*1001+1;
}
memcpy(c2,c,sizeof(c2));
maxf=getmax();
printf("%lld ",maxf/1001);
ans[0]=0;
for (int i=1;i<=m;i++)
{
if (maxf==0) break;
memcpy(c2,c,sizeof(c2));
c2[e[i].x][e[i].y]-=e[i].f;
long long now=getmax();
if (maxf-now==e[i].f)
{
c[e[i].x][e[i].y]-=e[i].f;
maxf-=e[i].f;
ans[0]++; ans[ans[0]]=i;
}
}
printf("%d\n",ans[0]);
for (int i=1;i<=ans[0];i++) printf("%d\n",ans[i]);
return 0;
}