首页 > 代码库 > HDU5556 Land of Farms(二分图 2015 合肥区域赛)

HDU5556 Land of Farms(二分图 2015 合肥区域赛)

容易想到将问题转化为求图的独立数问题 ,但求一般图的独立集是一个NPC问题,需要一些转化。

状态压缩,枚举每个上古农场是否选择,然后将剩下的新农场根据i + j奇偶性分为x , y集。

 

结果为 max(tot  + nx + ny - 二分图匹配数)

 

#include<cstdio>#include<iostream>#include<cstdlib>#include<cstring>#include<string>#include<algorithm>#include<map>#include<queue>#include<vector>#include<cmath>#include<utility>using namespace std;typedef long long LL;const int N = 150, INF = 0x3F3F3F3F;int mp[15][15];int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int cx[N], cy[N];//匹配结果int nx, ny;//x,y集合元素个数bool inx[N], iny[N];bool used[N];bool nop[15][15];//存x到y集合的有向图struct Node{    int to,next;}edge[1000];int head[N],tot;bool dfs(int u){    for(int i = head[u]; ~i; i = edge[i].next){        int v = edge[i].to;        if(!used[v]){            used[v] = true;            if(cy[v] == -1 || dfs(cy[v])){                cx[u] = v;                cy[v] = u;                return true;            }        }    }    return false;}int Hungary(){    int ans = 0;    memset(cx, -1, sizeof(cx));    memset(cy, -1, sizeof(cy));    for(int i = 0; i < nx; i++){        if(cx[i] == -1){            memset(used, 0, sizeof(used));            if(dfs(i)){                ans++;            }        }    }    return ans;}void init(){    memset(head, -1, sizeof(head));    tot = 0;}void add(int u, int to){    edge[tot].to=to;    edge[tot].next=head[u];    head[u]=tot++;}bool check(int n, int m, int st){    memset(nop, 0, sizeof(nop));    for(int i = 1; i <= n; i++){        for(int j = 1; j <= m; j++){            if(st & (1 << mp[i][j])){                for(int k = 0; k < 4; k++){                    int u = i + dir[k][0];                    int v = j + dir[k][1];                    if((mp[u][v] != -1) && (mp[i][j] != mp[u][v]) && (st & (1 << mp[u][v]))){                        return false;                    }                    nop[u][v] = 1;                }            }        }    }    return true;}char str[N];int main(){    int t, n, m;    cin>>t;    int vis[N];    for(int cas = 1; cas <= t; cas++){        scanf("%d %d", &n, &m);        int ans = 0;        memset(mp, -1, sizeof(mp));        memset(vis, 0, sizeof(vis));        for(int i = 1; i <= n; i++){            scanf("%s", str + 1);            for(int j = 1; j <= m; j++){                if(str[j] == ‘.‘){                    mp[i][j] = 10;                }else{                    mp[i][j] = str[j] - ‘0‘;                    vis[str[j] - ‘0‘] = 1;                }            }        }        int cnt = 0;        for(int i = 0; i < 10; i++){            if(vis[i]){                vis[i] = cnt++;            }        }        for(int i = 1; i <= n; i++){                for(int j = 1; j <= m; j++){                    if(mp[i][j] < 10){                        mp[i][j] = vis[mp[i][j]];                }            }        }        for(int st = 0; st < (1 << cnt); st++){            int tot = 0;            int tp = st;            while(tp){                tot += tp & 1;                tp >>= 1;            }            if(!check(n, m, st)){                continue;            }            init();            nx = 0;            ny = 0;            memset(inx, 0, sizeof(inx));            memset(iny, 0, sizeof(iny));            for(int i = 1; i <= n; i++){                for(int j = 1; j <= m; j++){                    if(mp[i][j] < 10){                        nop[i][j] = 1;                    }                    if((i + j) % 2){                        if(mp[i][j] == 10 && !nop[i][j]){                            iny[(i - 1) *m + j - 1] = 1;                        }                    }                    if((i + j) % 2 == 0){                        if(mp[i][j] == 10 && !nop[i][j]){                            inx[(i - 1) *m + j - 1] = 1;                            for(int k = 0; k < 4; k++){                                int u = i + dir[k][0];                                int v = j + dir[k][1];                                if(mp[u][v] == 10 && !nop[u][v]){                                    add((i - 1) *m + j - 1, (u - 1) *m + v - 1);                                }                            }                        }                    }                }            }            for(int i = 0; i < n * m; i++){                if(inx[i]){                    tot++;                    nx = i + 1;                }                if(iny[i]){                    tot++;                    ny = i + 1;                }            }            ans = max(ans, tot - Hungary());        }        printf("Case #%d: %d\n", cas, ans);    }    return 0;}

  

HDU5556 Land of Farms(二分图 2015 合肥区域赛)