USACO 4.4.2 追查坏牛奶 oj1341 网络流最小割问题

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

时间限制 Time Limitation
1s
注释 Hint
1s
来源 Source
usaco 4.4.2

不得不说这道题真的是毒，输出最小割，割的边数，以及割的方案。

因为只有1000条边，我们将每条边的流量*1001+1，求出最大流后/1001即是最大流【相信能理解】，%1001之后就是割的边数【这也很好理解】。

　　最难的第三个问题：输出割的方案。虽然可以通过：枚举每条边，先去掉这条边，然后再求最大流，如果最大流的减小值是这条边的权值，那么这条边就在内，输出即可。然而虽然数据量支持我们这么做，但是OJ的数据..........1000条1到4的边，流量都是2000000。虽然可以在评测姬变卡之后仍能过去【gy0.7s此点】，但是写的不知道为什么我自己本地0.9s。但是发现树神有更高级的写法：

　　从源点进行DFS遍历，如果到下一条边流量不为0，继续遍历标记。最后对于每个点枚举它的边，如果x到y有边，x标记，y为标记，说明这条边在最小割中。然而OJ是有数据卡这个方法的。这个方法求的边是第一个遇到的最小割，然而如果1 2 3 4四个点，之间流量都是10，边如下：3 4 10,2 3 10,1 2 10。因为题目要求给出多种方法，按边的序号字典序输出，这四个点割一条边，肯定是都可以的，正解是输出1【3 4这条边，序号为1】。但是图中按此法显然我们求出的是1 ，2。

　　我们便可以发现问题了。但是这种数据只能用来卡序号，这就需要此方法求得的这条边能导致后面不连通。那么显然这条边流量是满的。后面如果出现更优解【字典序更小】，那么也必须流量是满的，且流量一样，并满足边数等于前面。

　　但是，这也并不是正解，仍然会被卡掉。正解还是删边求最大流。

　　错误但能水过的代码：

 #include<bits/stdc++.h>

 #define ll long long

 #define INF 2100000000

 using namespace std;

 int level[];

 int q[];

 int lin[];

 int rev[];

 bool f[];

 bool fe[];

 int len=;

 ll ans=;

 int cnt[];

 struct www

 {

     ll v;

     int id;

 }a[][],b[][],c[];

 ll n,m;

 ll s,t;

 struct qaq{

     int nt,y;

     ll v;

 }e[];

 char buf[<<],*fs,*ft;

 inline char getc(){ return(fs==ft && (ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++; }

 ll read()

 {

     ll x=;

     char ch=getc();

     while(!isdigit(ch)) ch=getc();

     while(isdigit(ch)) {x=(x<<)+(x<<)+ch-''; ch=getc();}

     return x;

 }

 void insert(int x,int y,ll v)

 {

     e[++len].nt=lin[x]; e[len].v=v; e[len].y=y; lin[x]=len; rev[len]=len+; fe[len]=;

     e[++len].nt=lin[y]; e[len].v=; e[len].y=x; lin[y]=len; rev[len]=len-;

 }

 bool make_level()

 {

     ll head=,tail=;

     memset(level,-,sizeof(level));

     q[]=s;level[s]=;

     while(head++<tail)

     {

         ll x=q[head];

         for(ll i=lin[x];i;i=e[i].nt)

             if(e[i].v && level[e[i].y]==-)

             {

                 level[e[i].y]=level[x]+;

                 q[++tail]=e[i].y;

             }

     }

     return level[t]>=;

 }

 ll max_flow(ll k,ll flow)

 {

     if(k==t) return flow;

     ll maxflow=;

     ll v;

     for(ll i=lin[k];i && (maxflow<flow);i=e[i].nt)

         if(e[i].v && level[e[i].y]==level[k]+)

             if(v=max_flow(e[i].y,min(e[i].v,flow-maxflow)))

                 maxflow+=v,e[i].v-=v,e[rev[i]].v+=v;

     if(!maxflow) level[k]=-;

     return maxflow;

 }

 ll dinic()

 {

     ans=;

     ll v;

     while(make_level())

         while(v=max_flow(s,INF))

             ans+=v;

     return ans;

 }

 void dfs(int k)

 {

     f[k]=;

     for(int i=lin[k];i;i=e[i].nt)

     {

         if(!f[e[i].y]&&e[i].v)

             dfs(e[i].y);

     }

 }

 int main()

 {

     freopen("a.txt","r",stdin);

     freopen("b.txt","w",stdout);

     n=read();

     m=read();

     s=,t=n;

     for(ll i=;i<=m;++i)

     {

         int x=read(),y=read();

         ll v=read();

         c[i].v=v;

         insert(x,y,v*+);

     }

     ll tmp=dinic();

     //cout<<tmp<<endl;

     printf("%lld %lld\n",tmp/,tmp%);

     bool flag=;

     for(int i=;i<=m;i++)

         if(c[i].v==tmp/)

         {

             cout<<i<<endl;

             flag=;

         }

     if(flag==) return ;

     dfs();

     //cout<<"--------"<<endl;

     //for(int i=1;i<=n;i++) cout<<f[i]<<' ';cout<<endl;

     int haha=;

     for(int i=;i<=n;i++)

     {

         for(int j=lin[i];j;j=e[j].nt)

         {

             if(f[i]&&!f[e[j].y]&&fe[j])

                 cnt[++haha]=(j+)>>;

         }

     }

     sort(cnt+,cnt++haha);

     for(int i=;i<=haha;i++) cout<<cnt[i]<<endl;

     return ;

 }

　　正确的代码：

#include<bits/stdc++.h>

#define ll long long

#define INF 210000000

using namespace std;

struct qwq

{

    int st,ed;

    ll v;

    int id;

}ee[];

int n,m;

bool f[];

int num[];

int nnn=;

struct qaq

{

    int y,nt;

    ll v;

}e[];

int len=;

int rev[];

int lin[];

ll ans;

int level[];

int q[];

int s,t;

bool mycmp(qwq aa,qwq bb) {return aa.v>bb.v||(aa.v==bb.v&&aa.id<bb.id);}

void insert(int x,int y,ll v)

{

    e[++len].v=v; e[len].y=y; e[len].nt=lin[x]; lin[x]=len; rev[len]=len+;

    e[++len].v=; e[len].y=x; e[len].nt=lin[y]; lin[y]=len; rev[len]=len-;

}

bool make_level()

{

    memset(level,-,sizeof(level));

    int head=,tail=;

    q[tail]=s;

    level[s]=;

    while(head++<tail)

    {

        int x=q[head];

        for(int i=lin[x];i;i=e[i].nt)

            if(e[i].v&&level[e[i].y]==-)

            {

                level[e[i].y]=level[x]+;

                q[++tail]=e[i].y;

            }

    }

    return level[t]>=;

}

ll max_flow(int k,ll flow)

{

    if(k==t) return flow;

    ll d=;

    ll maxn=;

    for(int i=lin[k];i&&(maxn<flow);i=e[i].nt)

        if(e[i].v&&level[e[i].y]==level[k]+)

            if(d=max_flow(e[i].y,min(e[i].v,flow-maxn)))

                maxn+=d,e[i].v-=d,e[rev[i]].v+=d;

    if(!maxn) level[k]=-;

    return maxn;

}

ll dinic()

{

    ll tv=;

    ll td=;

    while(make_level())

        while(td=max_flow(s,INF))

            tv+=td;

    return tv;

}

void rebuild()

{

    memset(e,,sizeof(e));

    memset(lin,,sizeof(lin));

    len=;

    for(int i=;i<=m;i++)

    {

        if(f[ee[i].id]) continue;

        insert(ee[i].st,ee[i].ed,ee[i].v);

    }

}

void cut_line()

{

    sort(ee+,ee++m,mycmp);

    int cnt=;

    memset(f,,sizeof(f));

    for(int i=;i<=m;i++)

    {

        f[ee[i].id]=;

        rebuild();

        int tmp=dinic();

        if(tmp+cnt+ee[i].v==ans)

        {

            cnt+=ee[i].v;

            num[++nnn]=ee[i].id;

        }

        else f[ee[i].id]=;

    }

}

int main()

{

    //freopen("a.txt","r",stdin);

    scanf("%d%d",&n,&m);

    s=;t=n;

    for(int i=;i<=m;i++)

    {

        scanf("%d%d",&ee[i].st,&ee[i].ed);

        scanf("%lld",&ee[i].v);

        ee[i].id=i;

        insert(ee[i].st,ee[i].ed,ee[i].v*+);

    }

    ans=dinic();

    printf("%lld %lld\n",ans/,ans%);

    ans/=;

    cut_line();

    sort(num+,num++nnn);

    for(int i=;i<=nnn;i++) printf("%d\n",num[i]);

    return ;

}

巴特西

USACO 4.4.2 追查坏牛奶 oj1341 网络流最小割问题

最新文章

热门文章