[HOJ 157][POI 12 Stage 2] Dicing

神奇的轉成flow 的題目......不過用Edmonds-Karp 會TLE，只好學了一下Dinic ，不過 Dinic 也蠻直觀的，而且據說他在這種特殊圖的時間複雜度是 O(E^1.5)，在這題上就跑超快。

作法：

題目是問說要當冠軍至少要贏幾場，也就等價於問「對每條邊都取其中一個他連接的點當代表，每個點被選到的次數的最大值」的最小值。

首先最外層二分答案，這樣就變成判斷有沒有可能讓每條邊都選一個點當代表，使得每個點至多被選到 k 次。而這又可以反過來看，看成每個點可以占領根他連的 k 條邊，問有沒有辦法把邊占領完。

考慮一張圖，其中 n 個點是原圖的點，剩下的 m' 個點代表原圖的邊(把相同兩端點的邊融合起來)，建立最大流模型，加入源點 s 、匯點 t ，s 到 1~n 建一條容量為 k 的邊，從「代表邊的點」建一條容量為「這條邊出現了幾次」的邊到 t ，例如 a,b 兩點中間連了三條邊，那就在代表邊的點「ab」連一條到 t 的邊，容量為3。然後中間的話，建從 a 到 ab 的邊和從 b 到 ab 的邊，容量不要太小就好，我是直接設為 ab 連到 t 的容量。

建完圖後求 s-t 的最大流，如果流滿了那就有解，沒有流滿就無解，最後還要把它轉換為原本要取哪個端點，還蠻麻煩的就是了。

code :

#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
#define mkp(x,y) make_pair(x,y)
#define INF 100000000
using namespace std;
const int maxn=20000+100 ;
struct P{int from,to,flow,cap;};
vector<P> edge ;
vector<int> v[maxn] ;
 
int n,m ;
struct Dinic
{
    int st,ed ;
 
    void init(int num)
    {
        for(int i=0;i<edge.size();i++)
            edge[i].flow = 0 ;
        for(int i=0;i<n;i++) edge[2*i].cap=num ;
    }
 
    void add_edge(int from,int to,int cap)
    {
        edge.push_back((P){from,to,0,cap}) ;
        edge.push_back((P){to,from,0,0}) ;
        int z=edge.size() ;
        v[from].push_back(z-2) ;
        v[to].push_back(z-1) ;
    }
 
    bool vis[maxn] ;
    int d[maxn] ;
    bool BFS()
    {
        memset(vis,0,sizeof(vis)) ;
        queue<int> q ;
        d[st]=0 ; q.push(st) ; vis[st]=1 ;
        while(!q.empty())
        {
            int u=q.front() ; q.pop() ;
            for(auto i:v[u])
            {
                P &e=edge[i] ;
                if(!vis[e.to] && e.cap>e.flow)
                {
                    vis[e.to]=1 ;
                    d[e.to]=d[u]+1 ;
                    q.push(e.to) ;
                }
            }
        }
        return vis[ed] ;
    }
 
    int cur[maxn] ;
    int DFS(int x,int a)
    {
        if(x==ed || a==0) return a ;
        int Flow=0 , f ;
        for(int &i=cur[x];i<v[x].size();i++)
        {
            P &e=edge[v[x][i]] ;
            if(d[e.to]==d[x]+1 && (f=DFS(e.to,min(a,e.cap-e.flow)))>0)
            {
                Flow+=f ;
                e.flow+=f ;
                edge[v[x][i]^1].flow-=f ;
                a-=f ;
                if(a==0) break ;
            }
        }
        return Flow ;
    }
 
    int MaxFlow(int st,int ed)
    {
        this->st = st ;
        this->ed = ed ;
        int Flow=0 ;
        while(BFS())
        {
            memset(cur,0,sizeof(cur)) ;
            Flow+=DFS(st,INF) ;
        }
        return Flow ;
    }
}dinic ;
 
int Mflow ;
bool check(int num)
{
    dinic.init(num) ;
    if(dinic.MaxFlow(n+m+1,n+m+2)==Mflow) return 1 ;
    else return 0 ;
}
 
map<pii,int> mp ;
pii p[maxn],p2[maxn] ;
main()
{
    scanf("%d%d",&n,&m) ;
    int m0 ; m0=Mflow=m ;
    for(int i=1;i<=m;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        p[i]=mkp(x,y) ;
        if(x>y) swap(x,y) ;
        mp[mkp(x,y)]++ ;
    }
    m=mp.size() ;
 
    for(int i=1;i<=n;i++) dinic.add_edge(n+m+1,i,0) ;
 
    int cnt=0 ;
    for(auto i : mp)
    {
        cnt++ ;
        dinic.add_edge(i.F.F,n+cnt,i.S) ;
        dinic.add_edge(i.F.S,n+cnt,i.S) ;
        dinic.add_edge(n+cnt,n+m+2,i.S) ;
        p2[n+cnt]=i.F ;
    }
 
    int l=0 , r=Mflow+1 ;
    while(r-l>1)
    {
        int mid=(l+r)/2 ;
        if(check(mid)) r=mid ;
        else l=mid ;
    }
    check(r) ;
    printf("%d\n",r) ;
 
    mp.clear() ;
    for(auto i : edge)
        if(i.from<=m+n && i.to<=m+n && i.cap)
    {
        if(i.from == p2[i.to].F)
            mp[p2[i.to]]=i.flow ;
    }
 
    for(int i=1;i<=m0;i++)
    {
        if(p[i].F < p[i].S)
        {
            auto it=mp.find(p[i]) ;
            if(it->S)
            {
                printf("1\n") ;
                it->S-- ;
            }
            else printf("0\n") ;
        }
        else
        {
            auto it=mp.find(mkp(p[i].S,p[i].F)) ;
            if(it->S)
            {
                printf("0\n") ;
                it->S-- ;
            }
            else printf("1\n") ;
        }
    }
}