首页 > 代码库 > 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 合肥区域赛)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。