[codevs 1922] 騎士共存問題
題解：
二分圖最大獨立集問題。
二分圖的最大獨立集：
選出一些點，讓兩兩之間沒有邊相連。
二分圖最大獨立集問題一般轉化為它的對偶問題——最小覆蓋集，因為最大獨立集要求每條邊所連接的兩個點最多有一個被選中，而最小覆蓋集要求每條邊所連接的兩個點最少有一個被選中。那么點的個數-最小覆蓋集點的個數=最大獨立集（顯然減掉的越少剩下的越多）。
那么最小覆蓋怎么求呢？答案就是建立二分圖求最大基數匹配。可以簡單證明一下：
1）充分性：如果還有一條邊沒有被覆蓋，那么此時一定可以把這條邊作為一條新的匹配，說明此時還不是最大匹配。
2）必要性：如果可以刪去一條邊，二分圖匹配邊中是沒有交點的，那么刪去后這條邊一定不會被覆蓋。
算法就到此結束。
原題中記得要把總點數減去不能走的格子數。
代碼：
dinic算法過了，ISAP死活不對...應該是我寫的問題。
Dinic：
總時間耗費: 3172ms ?
總內存耗費: 11 kB
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;const int maxn = 200 * 200 + 10;
const int INF = 1e9 + 7;const int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1};
const int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};int n, m, s, t;struct Edge {int from, to, cap, flow;
};vector<Edge> edges;
vector<int> G[maxn];void AddEdge(int from, int to, int cap) {edges.push_back((Edge){from, to, cap, 0});edges.push_back((Edge){to, from, 0, 0});int sz = edges.size();G[from].push_back(sz-2);G[to].push_back(sz-1);
}int id[222][222];
void init() {cin >> n >> m;s = 0; t = n*n - m + 1;for(int i = 0; i < m; i++) {int x, y;cin >> x >> y;id[x][y] = -1;}int c = 0;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(!id[i][j]) id[i][j] = ++c;for(int x = 1; x <= n; x++)for(int y = 1; y <= n; y++) if(id[x][y] > 0) {int ID = id[x][y];if((x+y)%2 == 0) {AddEdge(s, ID, 1);for(int i = 0; i < 8; i++) {int newx = x + dx[i], newy = y + dy[i];int newID = id[newx][newy];if(newx <= n && newy <= n && newx >= 1 && newy >= 1 && newID > 0) AddEdge(ID, newID, INF);}} else {AddEdge(ID, t, 1);}}
}bool vis[maxn];
int d[maxn];
bool BFS() {queue<int> Q;Q.push(s);memset(vis, 0, sizeof(vis));d[s] = 0;vis[s] = 1;while(!Q.empty()) {int u = Q.front(); Q.pop();for(int i = 0; i < G[u].size(); i++) {Edge& e = edges[G[u][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[t];
}int cur[maxn];int DFS(int u, int a) {if(a == 0 || u == t) return a;int f, flow = 0;for(int& i = cur[u]; i < G[u].size(); i++) {Edge& e = edges[G[u][i]];if(d[u] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) {flow += f;e.flow += f;a -= f;edges[G[u][i]^1].flow -= f;if(a == 0) break;}}return flow;
}void Dinic() {int flow = 0;while(BFS()) {memset(cur, 0, sizeof(cur));flow += DFS(s, INF);}cout << n*n-m-flow << endl;
}int main() {init();Dinic();return 0;
}
ISAP：
TLE（哪錯了呢？）
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;const int maxn = 200 * 200 + 10;
const int INF = 1e9 + 7;const int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1};
const int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};int n, m, s, t;struct Edge {int from, to, cap, flow;
};vector<Edge> edges;
vector<int> G[maxn];void AddEdge(int from, int to, int cap) {edges.push_back((Edge){from, to, cap, 0});edges.push_back((Edge){to, from, 0, 0});int sz = edges.size();G[from].push_back(sz-2);G[to].push_back(sz-1);
}int id[222][222];
void init() {cin >> n >> m;s = 0; t = n*n - m + 1;for(int i = 0; i < m; i++) {int x, y;cin >> x >> y;id[x][y] = -1;}int c = 0;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(!id[i][j]) id[i][j] = ++c;for(int x = 1; x <= n; x++)for(int y = 1; y <= n; y++) if(id[x][y] > 0) {int ID = id[x][y];if((x+y)%2 == 0) {AddEdge(s, ID, 1);for(int i = 0; i < 8; i++) {int newx = x + dx[i], newy = y + dy[i];int newID = id[newx][newy];if(newx <= n && newy <= n && newx >= 1 && newy >= 1 && newID > 0) AddEdge(ID, newID, INF);}} else {AddEdge(ID, t, 1);}}
}bool vis[maxn];
int d[maxn], p[maxn], cur[maxn], num[maxn];int Augment() {int x = t, a = INF;while(x != 1) {Edge& e = edges[p[x]];a = min(a, e.cap-e.flow);x = e.from;}x = t;while(x != 1) {edges[p[x]].flow += a;edges[p[x]^1].flow -= a;x = edges[p[x]].from;}return a;
}void BFS() {queue<int> Q;bool vis[maxn];memset(vis, 0, sizeof(vis));d[t] = 0;Q.push(t);while(!Q.empty()) {int x = Q.front(); Q.pop();for(int i = 0; i < G[x].size(); i++) {Edge& e = edges[G[x][i]];if(e.cap == 0 && !vis[e.to]) {d[e.to] = d[x] + 1;vis[e.to] = 1;Q.push(e.to);}}}
} void Maxflow() {int flow = 0;BFS();memset(num, 0, sizeof(num));for(int i = 0; i <= t; i++) num[d[i]]++;int x = s;memset(cur, 0, sizeof(cur));while(d[s] < t) {if(x == t) {flow += Augment();x = s;}int ok = 0;for(int i = cur[x]; i < G[x].size(); i++) {Edge& e = edges[G[x][i]];if(e.cap > e.flow && d[x] == d[e.to] + 1) {ok = 1;p[e.to] = G[x][i];cur[x] = i;x = e.to;break;}}if(!ok) {int _m = t - 1;for(int i = 0; i < G[x].size(); i++) {Edge& e = edges[G[x][i]];if(e.cap > e.flow) _m = min(_m, d[e.to]);}if(--num[d[x]] == 0) break;num[d[x] = _m+1]++;cur[x] = 0;if(x != s) x = edges[p[x]].from;}}cout << n*n-m-flow << endl;
}int main() {init();Maxflow();return 0;
}我的ISAP連草地排水都WA一個點。。。
dinic算法過了，ISAP死活不對...應該是我寫的問題。
TLE
總結
以上是生活随笔為你收集整理的[codevs 1922] 骑士共存问题的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
