usaco_4_4_2_milk6-最大流最小割.cpp

usaco自己做的1到5章的代码

/*
PROB: milk6
LANG: C++
*/
/*
描述

你第一天接手光明牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批坏牛奶。很不幸，你发现这件事的时候，坏牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些坏牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。

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) 表示让这辆卡车停止运输的损失。


本题比较麻烦，要用到最小割最大流定理。首先求出最大流，那么最小割的容量就是最大流的流量。然后找有没有容量=最小割容量的“桥”（这里的桥就是去掉这条边后，由源点出发无法到达汇点），如果有那么这个桥就是答案。然后对每条容量不大于最小割的边，去掉后求一次最大流（估计这里我的算法太麻烦了）。如果流量的减少量=这条边的容量，那么这条边一定属于最小割。找出这样所有的边后，如果这些边的容量和=最小割容量，那么符合题目条件的最小割已求出。剩下的工作就是搜索了。用dfsid，每次增加深度限制，按边的编号大小顺序扩展，搜索是否存在一种方案使得这些边的权值与已求出的必然属于最小割的边的权值之和等于最小割。然后judge一下是否去掉这些边后源点与汇点不连通。如果不连通，则说明已经找到解，可直接输出。数据规模不算大，一般的BFS已经足可胜任最大流的工作。不过我用的是预流推进，最大数据也不超过0.1s。在熟练的前提下，还是尽量用更好的算法吧^_^。 

数据中可能存在两点之间有多条边的情况，可以在求最大流时把这些边并成一条边，然后在求最小割的边集时再拆开。
*/
#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define min(a,b) ((a)>(b)?(b):(a))
#define K1 500503
#define K2 1002
long long route[33][33],C=0;int N,M,r[1001][2],VIS[1001];
char l1[1000],l2[10000];
void ipd()
{
      FILE *ip;int i,p1,p2,c;
      ip=fopen("milk6.in","r");
      memset(route,0,sizeof(route));
      fscanf(ip,"%d%d",&N,&M);
      for(i=1;i<=M;++i)
      {
         fscanf(ip,"%d%d%d",&p1,&p2,&c);
         route[p1][p2]+=(long long)c*K1*K2+K1+i;
         r[i][0]=p1;r[i][1]=p2;
      }
      fclose(ip);
}
long long argu()
{
     int vis[33],pre[33],mloc,i;
     long long max,cap[33];
     memset(vis,0,sizeof(vis));
     memset(pre,0,sizeof(pre));
     memset(cap,0,sizeof(cap));
     cap[1]=(long long)(1047483647) * 2147483647;
     while(1)
     {
        max=0;mloc=0;
        for(i=1;i<=N;++i)
        {
           if(!vis[i]&&cap[i]>max)
           {max=cap[i];mloc=i;}
        }
        if(mloc==0)return 0;
        if(mloc==N)break;
        vis[mloc]=1;
        for(i=0;i<=N;++i)
        {
           if(route[mloc][i])
             if(cap[i]<min(route[mloc][i],max))
             {
                cap[i]=min(route[mloc][i],max);
                pre[i]=mloc;
             }
        }
     }
     i=N;max=cap[N];
     while(pre[i])
     {
        route[pre[i]][i]-=max;
        route[i][pre[i]]+=max;
        i=pre[i];
     }
     return max;
}
void dfs(int cur)
{
      int i;
      VIS[cur]=1;
      for(i=1;i<=N;++i)
      {
          if(!VIS[i]&&route[cur][i]>0)dfs(i);
      }
}
void opd()
{
      FILE *op;
      op=fopen("milk6.out","w");
      fprintf(op,"%s%s",l1,l2);
      fclose(op);
}
void debug()
{
      int i;
      for(i=1;i<=N;++i)printf("%d %d\n",i,VIS[i]);

}
int main(void)
{
     ipd();
     long long p,pn;int i,j,k;
     while((p=argu())>0.0)
     C+=p;
     sprintf(l1,"%d %d\n",(int)(C/(K2*K1)),(int)(pn=((C%(K1*K2))/K1)));
     memset(VIS,0,sizeof(VIS));
     dfs(1);
     k=0;l2[0]=0;
     for(i=1;i<=pn;++i)
     {
       for(j=k+1;j<=M;++j)
       if(VIS[r[j][0]]==1&&VIS[r[j][1]]==0)break;
       sprintf(l2,"%s%d\n",l2,j);
       k=j;
     }
     opd();
     debug();
     return 0;
}