POJ 3189 枚舉+最大流判可行性

這題即使不是我做過最坑的題，也是我今年遇到的有數的幾道惡心題。

題意思路什麼的都簡單不敘述了。

主要講一下這題坑的地方。

那就是。。。如果你邊的數組開小了，那麼就是TLE。沒錯，就是TLE。

這題我昨晚交了50發，一直T，我從頭到尾把DINIC代碼改了10遍以上，後來改的我一點脾氣都沒有了。

今天早上又來了10來發，還是T，我就從頭開始寫了一遍。這次抱著爆搞的心態，數組都開超大，沒想到A了。

我就XXXXXXXXX了。

然後我把數組重新改小了，還是T。

瞬間我把昨天晚上的代碼拿出來，改了下數組大小，也A了。

然後。。。就沒有然後了。。。我去吃飯了。。。

[cpp] 
#include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <string>  
#include <cmath>  
#include <cstring>  
#include <queue>  
#include <set>  
#include <vector>  
#include <stack>  
#include <map>  
#include <iomanip>  
#define PI acos(-1.0)  
#define Max 100005//把這個改成1W你試試就知道了親。親測哦。  
#define inf 1<<28  
#define LL(x) (x<<1)  
#define RR(x) (x<<1|1)  
#define REP(i,s,t) for(int i=(s);i<=(t);++i)  
#define ll long long  
#define mem(a,b) memset(a,b,sizeof(a))  
#define mp(a,b) make_pair(a,b)  
using namespace std; 
 
struct kdq 
{ 
    int s , e ,l, next ; 
} ed[Max] ; 
int head[1100] ,num ; 
void init() 
{ 
    mem(head,-1) ; 
    num = 0 ; 
} 
void add(int s, int e ,int l) 
{ 
    ed[num].s = s ; 
    ed[num].e = e ; 
    ed[num].l = l ; 
    ed[num].next = head[s] ; 
    head[s] = num ++ ; 
 
    ed[num].s = e ; 
    ed[num].e = s ; 
    ed[num].l = 0 ; 
    ed[num].next = head[e] ; 
    head[e] = num ++ ; 
} 
int cow[Max][100] ; 
int w[Max] ; 
int n , m ; 
int S, T; 
void build(int k,int k1) 
{ 
    S = 0 ; 
    T = n + m + 1 ; 
    REP(i,1,n) 
    { 
        REP(j,k,k1) 
        add(cow[i][j] ,i + m ,1) ; 
        add(i + m ,T,1) ; 
    } 
    REP(i,1,m)add(S,i,w[i]) ; 
} 
int deep[1100] ; 
int qe[Max * 100] ; 
int dinic_bfs() 
{ 
    mem(deep,-1) ; 
    deep[S] = 0 ; 
    int h = 0 ,t = 0 ; 
    qe[h ++ ] = S ; 
    while(h > t) 
    { 
        int tt = qe[t ++ ] ; 
        for (int i = head[tt] ; ~i ; i = ed[i].next ) 
        { 
            int e = ed[i].e ; 
            int l = ed[i].l ; 
            if(l > 0 && deep[e] == -1) 
            { 
                deep[e] = deep[tt] + 1 ; 
                qe[h ++ ] = e ; 
            } 
        } 
    } 
    return deep[T] != -1 ; 
} 
int dinic_dfs(int now ,int f) 
{ 
    if(now == T) return f ; 
    int flow = 0 ; 
    for (int i = head[now] ; ~i ; i = ed[i].next ) 
    { 
        int e = ed[i].e ; 
        int l = ed[i].l ; 
        if(l > 0 && (f - flow) > 0 && deep[e] == deep[now]  + 1) 
        { 
            int mm = min(l,f - flow) ; 
            int nn = dinic_dfs(e,mm) ; 
            flow += nn ; 
            ed[i].l -= nn ; 
            ed[i ^ 1].l += nn ; 
        } 
    } 
    if(!flow) deep[now] = -2 ; 
    return flow ; 
} 
 
int dinic() 
{ 
    int flow = 0 ; 
    while(dinic_bfs()) 
    { 
        flow += dinic_dfs(S,inf) ; 
    } 
    return flow ; 
} 
int solve() 
{ 
    int ans = inf ; 
    REP(i,1,m) 
    { 
        REP(j,i,m) 
        { 
            init() ; 
            build(i ,j) ; 
            int aa = dinic() ; 
            if(aa == n){ 
                ans = min(ans,j - i + 1) ; 
                if(ans == 1) 
                return ans ; 
            } 
        } 
    } 
    return ans ; 
} 
int main() 
{ 
#ifndef ONLINE_JUDGE  
    freopen("acm.txt", "r", stdin); 
#endif  
    scanf("%d%d",&n,&m) ; 
    REP(i,1,n)REP(j,1,m)scanf("%d",&cow[i][j]) ; 
    REP(i,1,m )scanf("%d",&w[i]) ; 
    printf("%d\n",solve()) ; 
    return 0; 
} 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 100005//把這個改成1W你試試就知道了親。親測哦。
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;

struct kdq
{
    int s , e ,l, next ;
} ed[Max] ;
int head[1100] ,num ;
void init()
{
    mem(head,-1) ;
    num = 0 ;
}
void add(int s, int e ,int l)
{
    ed[num].s = s ;
    ed[num].e = e ;
    ed[num].l = l ;
    ed[num].next = head[s] ;
    head[s] = num ++ ;

    ed[num].s = e ;
    ed[num].e = s ;
    ed[num].l = 0 ;
    ed[num].next = head[e] ;
    head[e] = num ++ ;
}
int cow[Max][100] ;
int w[Max] ;
int n , m ;
int S, T;
void build(int k,int k1)
{
    S = 0 ;
    T = n + m + 1 ;
    REP(i,1,n)
    {
        REP(j,k,k1)
        add(cow[i][j] ,i + m ,1) ;
        add(i + m ,T,1) ;
    }
    REP(i,1,m)add(S,i,w[i]) ;
}
int deep[1100] ;
int qe[Max * 100] ;
int dinic_bfs()
{
    mem(deep,-1) ;
    deep[S] = 0 ;
    int h = 0 ,t = 0 ;
    qe[h ++ ] = S ;
    while(h > t)
    {
        int tt = qe[t ++ ] ;
        for (int i = head[tt] ; ~i ; i = ed[i].next )
        {
            int e = ed[i].e ;
            int l = ed[i].l ;
            if(l > 0 && deep[e] == -1)
            {
                deep[e] = deep[tt] + 1 ;
                qe[h ++ ] = e ;
            }
        }
    }
    return deep[T] != -1 ;
}
int dinic_dfs(int now ,int f)
{
    if(now == T) return f ;
    int flow = 0 ;
    for (int i = head[now] ; ~i ; i = ed[i].next )
    {
        int e = ed[i].e ;
        int l = ed[i].l ;
        if(l > 0 && (f - flow) > 0 && deep[e] == deep[now]  + 1)
        {
            int mm = min(l,f - flow) ;
            int nn = dinic_dfs(e,mm) ;
            flow += nn ;
            ed[i].l -= nn ;
            ed[i ^ 1].l += nn ;
        }
    }
    if(!flow) deep[now] = -2 ;
    return flow ;
}

int dinic()
{
    int flow = 0 ;
    while(dinic_bfs())
    {
        flow += dinic_dfs(S,inf) ;
    }
    return flow ;
}
int solve()
{
    int ans = inf ;
    REP(i,1,m)
    {
        REP(j,i,m)
        {
            init() ;
            build(i ,j) ;
            int aa = dinic() ;
            if(aa == n){
                ans = min(ans,j - i + 1) ;
                if(ans == 1)
                return ans ;
            }
        }
    }
    return ans ;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("acm.txt", "r", stdin);
#endif
    scanf("%d%d",&n,&m) ;
    REP(i,1,n)REP(j,1,m)scanf("%d",&cow[i][j]) ;
    REP(i,1,m )scanf("%d",&w[i]) ;
    printf("%d\n",solve()) ;
    return 0;
}