USACO 5.4.5 TeleCowmunication 奶牛的電信 telecow

算法和4.4的pollutant control(求最小邊割集)類似,但這道題是求最小點割集。

我們可以把每個點i拆成兩個點i1,i2,這兩個點之間建立一條邊權爲1的有向弧。對於原圖中邊(i,j),建立(i2,j1)和(j2,i1)兩條邊權爲∞的有向弧。這樣就把求最小點割轉化成了求最小邊割。

根據最大流最小割定理:源S到匯T的網絡最大流等於S與T間最小邊割集的容量和。只需對新圖求網絡最大流,記爲netflow,在這裏我用了Dinic。這樣就完成了第一問,結果爲netflow。

對於第二問,要求出最小割集。對於每個點i(非c1,c2),把邊(i1,i2)去掉,求最大流,記爲nowflow,記當前找到的最小割集中元素的數量爲cnt。如果netflow-cnt=nowflow+1,那麼點i一定是最小割集中的割點,記錄下來。否則將邊(i1,i2)重新加上。直到cnt=netflow,當前找的集合就是最小割集。

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3644 KB]
   Test 2: TEST OK [0.011 secs, 3640 KB]
   Test 3: TEST OK [0.011 secs, 3644 KB]
   Test 4: TEST OK [0.000 secs, 3644 KB]
   Test 5: TEST OK [0.000 secs, 3640 KB]
   Test 6: TEST OK [0.011 secs, 3640 KB]
   Test 7: TEST OK [0.000 secs, 3644 KB]
   Test 8: TEST OK [0.011 secs, 3640 KB]
   Test 9: TEST OK [0.032 secs, 3640 KB]
   Test 10: TEST OK [0.054 secs, 3644 KB]
   Test 11: TEST OK [0.097 secs, 3640 KB]

All tests OK.

Your program ('telecow') produced all correct answers!  This is your
submission #5 for this problem.  Congratulations!

第一次寫Dinic,很冗長。

/*
ID: cmykrgb1
PROG: telecow
LANG: C++
*/

#include <iostream>
#include <fstream>
#define MAX 201
#define INF 0x7FFFFFFF

using namespace std;

class Tadjl
{
public:
    int cnt;
    int to[MAX];
    Tadjl(){cnt=0;}
    void ins(int k){to[++cnt]=k;}
};

class Tqueue
{
private:
    long first,last;
    long list[MAX*MAX];
public:
    long size;

    Tqueue()
    {
        reset();
    }

    void reset()
    {
        first=1;
        last=size=0;
    }

    void ins(long k)
    {
        size++;
        list[++last]=k;
    }

    long del()
    {
        size--;
        return list[first++];
    }
};

class Tstack
{
public:
    int stack[MAX];
    int top;
    int min,p;
    void reset()
    {
        top=0;
        min=INF;
    }

    Tstack()
    {
        reset();
    }
    void ins(int k)
    {
        stack[++top]=k;
    }
    void del()
    {
        top--;
    }
};

ifstream fi("telecow.in");
ofstream fo("telecow.out");
Tqueue Q;
Tstack AP;
int c1,c2,RN,RM,S,T,netflow;
Tadjl adjl[MAX];
int odis[MAX][MAX],dis[MAX][MAX],Flow[MAX][MAX];
int level[MAX],set[MAX];
bool used[MAX];

void init()
{
    int i,a,b,a1,a2,b1,b2,c;
    fi >> RN >> RM >> c1 >> c2;
    if (c1>c2) {c=c1;c1=c2;c2=c;}
    for (i=1;i<=RN;i++)
    {
        a=i*2-1;b=i*2;
        adjl[a].ins(b);
        dis[a][b]=1;
        adjl[b].ins(a);
        dis[b][a]=0;
    }
    for (i=1;i<=RM;i++)
    {
        fi >> a >> b;
        if (a>b) {c=a;a=b;b=c;}
        a1=a*2-1;a2=a1+1;
        b1=b*2-1;b2=b1+1;
        adjl[a2].ins(b1);
        dis[a2][b1]=INF;
        adjl[b1].ins(a2);
        dis[b1][a2]=0;
        adjl[b2].ins(a1);
        dis[b2][a1]=INF;
        adjl[a1].ins(b2);
        dis[a1][b2]=0;
    }
    S=c1*2;
    adjl[T=c2*2-1].cnt=0;
    memcpy(odis,dis,sizeof(dis));
}

void Dinic_level()
{
    int i,j,k;
    Q.reset();
    memset(used,0,sizeof(used));
    memset(level,0,sizeof(level));
    Q.ins(S);
    while (Q.size)
    {
        i=Q.del();
        used[i]=true;
        for (k=1;k<=adjl[i].cnt;k++)
        {
            j=adjl[i].to[k];
            if (!dis[i][j]) continue;
            if (used[j] || j==1) continue;
            level[j]=level[i]+1;
            Q.ins(j);
        }
    }
}

void Dinic_Argument()
{
    int i,u,v;
    AP.stack[0]=S;
    for (i=1;i<=AP.top;i++)
    {
        u=AP.stack[i-1];
        v=AP.stack[i];
        if (dis[u][v]<AP.min)
        {
            AP.min=dis[u][v];
            AP.p=u;
        }
    }
    for (i=AP.top;i>=1;i--)
    {
        u=AP.stack[i-1];
        v=AP.stack[i];
        Flow[u][v]+=AP.min;
        dis[u][v]-=AP.min;
        dis[v][u]+=AP.min;
    }
}

bool Dinic_dfs(int u)
{
    int outdegree=0;
    int i,v;
    bool B;
    if (u!=T)
    {
        for (i=1;i<=adjl[u].cnt;i++)
        {
            v=adjl[u].to[i];
            if (level[v]==level[u]+1 && dis[u][v])
            {
                outdegree++;
                AP.ins(v);
                B=Dinic_dfs(v);
                AP.del();
                if (B && u!=AP.p)
                    return true;
            }
        }
        if (outdegree==0)
            level[u]=0;
    }
    else
    {
        Dinic_Argument();
        return true;
    }
    return false;
}

void Dinic()
{
    memset(Flow,0,sizeof(Flow));
    for (;;)
    {
        Dinic_level();
        if (level[T]==0)
            return;
        AP.reset();
        Dinic_dfs(S);
    }
}

int getflow()
{
    int i,flow=0;
    for (i=1;i<=RN*2;i++)
        flow+=Flow[S][i];
    return flow;
}

void Getset()
{
    int i,a,b,nowflow,cnt=0;
    Dinic();
    netflow=getflow();


    for (i=1;i<=RN;i++)
    {
        if (i!=c1 && i!=c2)
        {
            a=i*2-1;b=a+1;
            odis[a][b]=0;
            memcpy(dis,odis,sizeof(odis));
            Dinic();
            nowflow=getflow();
            if (nowflow+1==netflow-cnt)
                set[++cnt]=i;
            else
                odis[a][b]=1;
        }
        if (cnt==netflow)
            return;
    }
}

void print()
{
    int i;
    fo << netflow << endl << set[1];

    for (i=2;i<=netflow;i++)
        fo <<' ' << set[i];
    fo << endl;
    fi.close();
    fo.close();
}

int main()
{
    init();
    Getset();
    print();
    return 0;
}

相關日誌