Pollutant Control
Hal Burch
It's your first day in Quality Control at Merry Milk Makers, and already there's been a catastrophe: a shipment of bad milk has been sent out. Unfortunately, you didn't discover this until the milk was already into your delivery system on its way to stores. You know which grocer that milk was destined for, but there may be multiple ways for the milk to get to that store.
The delivery system is made up of a several warehouses, with trucks running from warehouse to warehouse moving milk. While the milk will be found quickly, it is important that it does not make it to the grocer, so you must shut down enough trucks to ensure that it is impossible for the milk to get to the grocer in question. Every route costs a certain amount to shut down. Find the minimum amount that must be spent to ensure the milk does not reach its destination, along with a set of trucks to shut down that achieves this goal at that cost.
PROGRAM NAME: milk6
INPUT FORMAT
Line 1: Two space separated integers, N and M. N (2 <= N <= 32) is the number of warehouses that Merry Milk Makers has, and M (0 <= M <= 1000) is the number of trucks routes run. Warehouse 1 is actually the productional facility, while warehouse N is the grocer to which which the bad milk was destined.
Line 2..M+1: Truck routes: three space-separated integers, Si, Ei, and Ci. Si and Ei (1 <= Si,Ei <= N) correspond to the pickup warehouse and dropoff warehouse for the truck route. Ci (0 <= Ci <= 2,000,000) is the cost of shutting down the truck route.
SAMPLE INPUT (file milk6.in)
4 5
1 3 100
3 2 50
2 4 60
1 2 40
2 3 80
OUTPUT FORMAT
The first line of the output should be two integers, C and T. C is the minimum amount which must be spent in order to ensure the our milk never reaches its destination. T is the minimum number of truck routes that you plan to shut down in order to achive this goal. The next T lines sould contain a sorted list of the indexes of the truck routes that you suggest shutting down. If there are multiple sets of truck routes that achieve the goal at minimum cost, choose one that shuts down the minimum number of routes. If there are still multiple sets, choose the one whose initial routes have the smallest index.
SAMPLE OUTPUT (file milk6.out)
60 1
3
--------------------------------------------------------------------------------
非常繁琐的一道题。
求最小割，不仅要求割的权值，还有求割包含的所有的边。
大致思路是这样的。
先求最大流，把每条边的权值作相应的变化，
当最大流求出来之后，运用flood进行寻找一个最小割。
主要注意的情况有下列几种：
1：两点之间可能存在重边。
2：如果存在多个割集，取数目最小或者其中边的index最小的情况。
求最大流的问题参见之前的日志
/*
ID:yunleis3
PROG:milk6
LANG:C++
*/
#include <fstream>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=33;
const int maxm=1001;
#define DEBUG1 0
int n,m;
class edge
{
public:
int sec;
edge * next;
edge(int s,edge *n):sec(s),next(n){}
edge(){sec=0;next=NULL;}
};
int edges[maxm][4];
edge vertex[maxn];
bool visited[maxn];
int minie[maxn];
int preve[maxn];
int critedge[maxn];
int result[maxm];
int result1[maxm];
bool priodelete[maxm];
int minied[maxn];
int rptr=0;
int rptr1=0;
int totalpathvalue=0;
void quicksort(int * a,int p,int r);
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
int main()
{
ifstream fin("milk6.in");
fin>>n>>m;
for(int i=1;i<=m;++i){
int a,b,c;
fin>>a>>b>>c;
edges[i][0]=b;
edges[i][1]=c;
edges[i][2]=a;
edges[i][3]=c;
vertex[a].next=new edge(i,vertex[a].next);
}
bool flag=true;
edges[0][0]=1;
edges[0][1]=0;
edges[0][2]=0;
vertex[0].next=new edge(0,NULL);
visited[0]=true;
while(flag){
for(int i=1;i<=n;++i){
minie[i]=-1;
visited[i]=false;
preve[i]=-1;
}
// minie[1]=1;//wight of the edge to the targe;
// preve[1]=0;
// int finale=-1;
edge * etpm=&vertex[1];
while(etpm->next!=NULL){
int target=edges[etpm->next->sec][0];
if(minie[target]==-1||minie[target]<edges[etpm->next->sec][1])
{
minie[target]=edges[etpm->next->sec][1];
preve[target]=etpm->next->sec;
critedge[target]=etpm->next->sec;
}
etpm=etpm->next;
}
visited[1]=true;
while(true){
//find the mini edge;
int miniptr=-1;
for(int i=1;i<=n;++i){
if(!visited[i]&&minie[i]!=-1&&minie[i]!=0){
if(miniptr==-1||minie[i]>minie[miniptr])
miniptr=i;
else if(minie[i]==minie[miniptr]&&priodelete[critedge[i]])
{
miniptr=i;
}
}
}
if(miniptr==-1)
{
flag=false;
break;
}
if(miniptr==n)
{
break;
}
visited[miniptr]=true;
edge * crit=&vertex[miniptr];
while(crit->next!=NULL){
int target=edges[crit->next->sec][0];
if(!visited[target]&&(minie[target]==-1||(minie[target]<=min(minie[miniptr],edges[crit->next->sec][1])))){
minie[target]=min(minie[miniptr],edges[crit->next->sec][1]);
preve[target]=crit->next->sec;
critedge[target]=minie[miniptr]>edges[crit->next->sec][1]?crit->next->sec:miniptr;
}
crit=crit->next;
}
}
if(!flag)
break;
int xptr=n;
int pathvalue=-1;
int xxptr=-1;
while(xptr!=1){
int pree=preve[xptr];
if(pathvalue==-1||pathvalue>edges[pree][1])
{
pathvalue=edges[pree][1];
xxptr=pree;
}
else if(pathvalue==-1||(pathvalue==edges[pree][1]&&priodelete[pree]&&!priodelete[xxptr]))
{
//pathvalue=edges[pree][1];
xxptr=pree;
}
xptr=edges[pree][2];
}
xptr=n;
if(pathvalue==-1||pathvalue==0)
break;
result[rptr++]=xxptr;
totalpathvalue+=pathvalue;
while(xptr!=1){
int pree=preve[xptr];
edges[pree][1]-=pathvalue;
priodelete[pree]=true;
xptr=edges[pree][2];
}
}
//flood fill
queue<int> q;
q.push(1);
for(int i=0;i<=n;++i)
visited[i]=false;
queue<int> rs;
while(true){
while(!q.empty()){
int xx=q.front();
q.pop();
if(visited[xx])
continue;
visited[xx]=true;
edge * etmp=&vertex[xx];
bool flag=false;
while(etmp->next!=NULL){
if(edges[etmp->next->sec][1]>0){
q.push(edges[etmp->next->sec][0]);
//flag=true;
}
etmp=etmp->next;
}
//if(!flag){
//rs.push(xx);
//}
}
#if DEBUG1
for(int i=1;i<=m;++i){
if(edges[i][1]==0){
cout<<i<<" "<< edges[i][2]<<" "<<edges[i][0]<<" "<<edges[i][1]<<" "<<visited[edges[i][2]]<<" "<<visited[edges[i][0]]<<endl;
}
}
#endif
for(int i=1;i<n;++i){
if(visited[i]){
edge * etmp=&vertex[i];
while(etmp->next!=NULL){
if(!visited[edges[etmp->next->sec][0]]){
rs.push(i);
break;
}
etmp=etmp->next;
}
}
}
int tmp[maxm];
int tmpptr=0;
bool flag=false;
while(!rs.empty()){
int xx=rs.front();
rs.pop();
edge * etmp=&vertex[xx];
while(etmp->next!=NULL){
bool flag1=false;
for(int i=0;i<tmpptr;++i)
if(tmp[i]==etmp->next->sec)
flag1=true;
if(!flag){
q.push(edges[etmp->next->sec][0]);
}
if(edges[etmp->next->sec][1]==0){
tmp[tmpptr++]=etmp->next->sec;
if(edges[etmp->next->sec][0]==n)
flag=true;
}
etmp=etmp->next;
}
}
if(tmpptr==0)
break;
if(tmpptr!=0&&(rptr1==0||rptr1>tmpptr)){
rptr1=0;
for(int i=0;i<tmpptr;++i)
result1[rptr1++]=tmp[i];
}
else if(rptr1==tmpptr){
int i=0;
while(result1[i]==tmp[i])
++i;
if(result1[i]>tmp[i])
while(i<rptr1)
result1[i++]=tmp[i];
}
if(flag)
break;
}
/* for(int i=0;i<rptr;++i){
int first=edges[result[i]][2], second=edges[result[i]][0];
if(visited[first]&&!visited[second])
result1[rptr1++]=result[i];
}
*/
quicksort(result1,0,rptr1-1);
ofstream fout("milk6.out");
fout<<totalpathvalue<<" "<<rptr1<<endl;
for(int i=0;i<rptr1;++i){
fout<<result1[i]<<endl;
}
//system("pause");
for(int i=1;i<=n;++i){
while(vertex[i].next!=NULL){
edge * ptr=vertex[i].next;
vertex[i].next=ptr->next;
delete ptr;
}
}
}
void swap(int * a,int *b){
if(a==b)
return;
int x=*a;
*a=*b;
*b=x;
}
int partition(int *a,int p,int r){
int x=a[r];
int i=p-1;
for(int j=p;j<r;++j){
if(a[j]<x){
++i;
swap(a+i,a+j);
}
}
++i;
swap(a+r,a+i);
return i;
}
void quicksort(int * a,int p,int r){
if(p<r){
int q=partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}
/*
int n,m;
int metri[maxn][maxn];
int trucknum[maxn][maxn];
int result[maxm];
int resultvalue=0;
bool visited[maxn];
int minial[maxn];
int preve[maxn];
int rptr=0;
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
int main()
{
ifstream fin("milk6.in");
fin>>n>>m;
for(int i=0;i<=n;++i){
for(int j=0;j<=n;++j)
metri[i][j]=-1;
}
for(int i=0;i<m;++i){
int a,b,c;
fin>>a>>b>>c;
metri[a][b]=c;
trucknum[a][b]=i+1;
}
bool flag=true;
while(flag){
for(int i=1;i<=n;++i){
visited[i]=false;
minial[i]=metri[1][i];
preve[i]=1;
}
visited[1]=true;
while(true){
int miniptr=-1;
for(int i=1;i<=n;++i){
if(!visited[i]&&minial[i]!=-1){
if(miniptr==-1)
miniptr=i;
else if(minial[i]>minial[miniptr])
miniptr=i;
}
}
if(miniptr==n)
break;
if(miniptr==-1)
{
flag=false;
break;
}
visited[miniptr]=true;
for(int i=1;i<=n;++i){
if(!visited[i]){
if(minial[i]==-1&&(minial[miniptr]!=1&&metri[miniptr][i]!=1))
{
//minial[i]=minial[miniptr]+metri[miniptr][i];
preve[i]=miniptr;
minial[i]=min(minial[miniptr],metri[miniptr][i]);
}
else if(minial[i]!=-1&&(minial[miniptr]!=1&&metri[miniptr][i]!=1))
{
//minial[i]=minial[miniptr]+metri[miniptr][i];
if(min(minial[miniptr],metri[miniptr][i])<minial[i])
{
preve[i]=miniptr;
minial[i]=min(minial[miniptr],metri[miniptr][i]);
}
}
}
}
}
//find the minial value;
if(!flag)
break;
int pathvalue=-1;
int miniptr1=n;
int xptr=-1;
while(miniptr1!=1){
if(pathvalue==-1||(pathvalue>=metri[preve[miniptr1]][miniptr1]))
{
pathvalue=metri[preve[miniptr1]][miniptr1];
xptr=miniptr1;
}
miniptr1=preve[miniptr1];
}
if(pathvalue==-1||pathvalue==0)
break;
result[rptr++]=trucknum[preve[xptr]][xptr];
resultvalue+=pathvalue;
miniptr1=n;
//assert(pathvalue==-1);
while(miniptr1!=1){
metri[preve[miniptr1]][miniptr1]-=pathvalue;
miniptr1=preve[miniptr1];
}
}
ofstream fout("milk6.out");
cout<<resultvalue<<" "<<rptr<<endl;
for(int i=0;i<rptr;i++)
cout<<result[i]<<endl;
system("pause");
}
*/
