【ボード】Dinicアルゴリズム

Dinicアルゴリズムについて

引用Dinicは、ネットワークの最大ストリームを解く古典的なアルゴリズムの1つであり、最も簡単であるが効率が足りない拡張アルゴリズムを探すことによって最適化されている.

実現1.建図2.BFSは階層図を構築し、ソースポイントからポイントへの現在の最短パス

が存在するか否かを判断する.

bool Bfs() {
    memset(lev,0,sizeof(lev));//        lev[]
    int t; queue<int>q;
    q.push(S),lev[S]=1;
    while(!q.empty()) {
        t=q.front(),q.pop();
        for(int i=hd[t];i;i=nxt[i])
            if(!lev[to[i]]&&c[i]>0) { //  Dfs           c，    
                lev[to[i]]=lev[t]+1;
                if(to[i]==T) return 1;
                q.push(to[i]);
            }
    }
    return lev[T];
}

        3.存在する場合、DFSは、ソースポイントから集約ポイントへの経路を拡張し、すなわち、拡張路上容量が最小となる経路容量Fminを見つけ、拡張路上の経路流量を更新する.増広路が见つからなくなるまで缲り返した.

int Dfs(int x,int mx) {
    if(x==T||!mx) return mx; //           
    int f;
    for(int i=cur[x]?cur[x]:hd[x];i;i=nxt[i]) { //cur[i]    i    
        cur[x]=i; 
        if(lev[to[i]]==lev[x]+1&&c[i]>0) { //         
            if(f=Dfs(to[i],Min(mx,c[i]))) // Fmin
                return c[i]-=f,c[i^1]+=f,f; // i     i^1   tot       
        }
    }
    return 0;
}

繰り返し

int Dinic() {
    int f,Flow=0;
    while(Bfs()) {
        memset(cur,0,sizeof(cur));
        while(f=Dfs(S,Inf)) Flow+=f;
    }
    return Flow;
}

        4.そうでなければ最大ストリームが得られ,アルゴリズムが終了する

例題

6001.「ネットワークストリーム24題」宇宙飛行計画

タイトルの説明

W教授は国家宇宙センターのために一連の宇宙飛行を計画している.宇宙飛行のたびに一連の商業的な実験を行い、利益を得ることができる.選択可能な実験集合E={E 1,E 2,⋯,Em}E={E_1,E_2,cdots,E_m}E={E 1,E 2,⋯,E m}と,これらの実験を行うために使用するすべての機器の集合I={I 1,I 2,⋯,In}I={I_1,I_2,cdots,I_n}I={I 1,I 2,{I 2,I 2,cdots,I_n}I={I 1,I 2,⋯,I n}が決定された.実験Ej E_jE jが必要とする機器はI IIのサブセットRj⊆I R_であるj\subseteq IR​j​​⊆I.
設定機器Ik I_kIkの料金はck c_kc kドルです.実験Ej E_jE jのスポンサーは、この実験結果にpj p_を支払うことに同意した.jp jドルです.W教授の任務は、1回の宇宙飛行でどのような実験を行い、そのためにどの機器を配置すれば宇宙飛行の純収益を最大にすることができるかを決定する有効なアルゴリズムを見つけることだ.ここで純利益とは,実験を行って得られた全収入と配置機器の全費用との差額である.
与えられた実験と機器の配置状況に対して、プログラミングは純収益の最大の試験計画を探し出す.

入力フォーマット

1行目には正の整数mとnが2つあります.mは実験数,nは計器数である.次のm行は,各行が実験に関するデータである.最初のスポンサーはこの実験の費用を支払うことに同意した.次に、この実験に必要ないくつかの機器の番号です.最後の行のn個数は各機器を配置する費用である.

出力フォーマット

行目は実験番号,2行目は計器番号,最後の行は純収益である.

サンプル

サンプル入力

10 1 2
25 2 3
5 6 7

サンプル出力

1 2 3
17

データ範囲とヒント

1≤n,m≤50

ぶんせき

この問題は、最大重みを解く閉じた図(変換)->最小割合を解く(変換)->最大ストリームを解く具体的な変換過程スタンプここでhiho 119週目の最大重み閉じたサブ図を解く
最終最大ストリームの解はDinicアルゴリズムを用いる

コード#コード#

#include
#include
#include
using namespace std;

const int sm = 105,sn = 2505;
const int Inf = 0x3f3f3f3f;

int N,M,tot=1,sum,S,T,Flow;
int to[sn],hd[sm],nxt[sn],c[sn];
int lev[sm],cur[sm];
int a[sm],b[sm][sm],ct[sm];
bool ex[sm];

int Min(int x,int y) { return xchar ch;
void read(int &x) {
    x=0;ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
void Add(int u,int v,int w) {
    to[++tot]=v,nxt[tot]=hd[u],hd[u]=tot,c[tot]=w;
}
bool Bfs(int S,int T) {
    memset(lev,0,sizeof(lev));
    queue<int>q;
    q.push(S),lev[S]=1;
    while(!q.empty()) {
        int t=q.front();q.pop();
        for(int i=hd[t];i;i=nxt[i]) 
            if(!lev[to[i]]&&c[i]) {
                lev[to[i]]=lev[t]+1;
                if(to[i]==T) return 1;
                q.push(to[i]);
            }
    }
    return lev[T];
}
int Dfs(int x,int mx) {
    if(!mx||x==T) return mx;
    int f=0;
    for(int i=cur[x]?cur[x]:hd[x];i;i=nxt[i]) {
        cur[x]=i;
        if(c[i]&&lev[to[i]]==lev[x]+1) {
            if(f=Dfs(to[i],Min(mx,c[i])))
                return c[i]-=f,c[i^1]+=f,f;
        }
    }
    return 0;
}
void Dinic() {
    int f=0;
    while(Bfs(S,T)) {
        memset(cur,0,sizeof(cur));
        while(f=Dfs(S,Inf))Flow+=f;
    }
}
void DFS(int x,int b) {
    ex[x]=b;
    for(int i=hd[x];i;i=nxt[i])
        if(c[i]&&!ex[to[i]])
            DFS(to[i],b+1);
}
int main() {
    read(M),read(N);
    for(int i=1;i<=M;++i) {
        read(a[i]);sum+=a[i];
        while(ch!='
') {
            read(b[i][++ct[i]]); b[i][ct[i]]+=M;
            Add(i,b[i][ct[i]],Inf);
            Add(b[i][ct[i]],i,0);
        }
    }
    for(int i=1;i<=N;++i) read(a[i+M]);
    S=N+M+1; T=S+1;
    for(int i=1;i<=M;++i) 
        Add(S,i,a[i]),Add(i,S,0);
    for(int i=M+1;i<=M+N;++i)
        Add(i,T,a[i]),Add(T,i,0);

    Dinic();    

    DFS(S,1);

    for(int i=1;i<=M;++i)
        if(ex[i]) printf("%d ",i); putchar(10);
    for(int i=1;i<=N;++i)
        if(ex[M+i]) printf("%d ",i); putchar(10);
    printf("%d
",sum-Flow);
    return 0;
}