題意：給你n張照片的范圍，n個點的坐標(biāo)，問你能唯一確定那幾個點屬于那幾張照片，例如樣例中4唯一屬于A，2唯一屬于C，1唯一屬于B，3唯一屬于C

思路：進(jìn)行二分圖完全匹配，怎么判斷唯一屬于？匹配完之后刪掉某一條匹配邊再跑一次二分圖匹配，如果還能完全匹配，那么就不是唯一，反之唯一。

代碼：

#include<set> #include<map> #include<stack> #include<cmath> #include<queue> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<sstream> #include<iostream> #include<algorithm> typedef long long ll; using namespace std; const int maxn = 100 + 10; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; struct node{int x1, x2, y1, y2; }p[maxn]; struct Node{int x, y; }a[maxn]; struct Edge{int to, next; }edge[maxn * 4]; int g[maxn][maxn], linker[maxn], ans[maxn], n; bool used[maxn]; bool dfs(int u){for(int v = 0; v < 2 * n; v++){if(g[u][v] && !used[v]){used[v] = true;if(linker[v]== -1 || dfs(linker[v])){linker[v] = u;return true;}}}return false; } int hungary(){int res = 0;memset(linker, -1, sizeof(linker));for(int u = 0; u < 2 * n; u++){memset(used, false, sizeof(used));if(dfs(u)) res++;}return res; } bool inside(node m, Node n){if(n.x > m.x1 && n.x < m.x2 && n.y > m.y1 && n.y < m.y2) return true;return false; } int main(){int ca = 1;while(~scanf("%d", &n) && n){for(int i = 0; i < n; i++){scanf("%d%d%d%d", &p[i].x1, &p[i].x2, &p[i].y1, &p[i].y2);}memset(g, 0, sizeof(g));for(int i = 0; i < n; i++){scanf("%d%d", &a[i].x, &a[i].y);for(int j = 0; j < n; j++){if(inside(p[j], a[i])){g[i][n + j] = g[n + j][i] = 1;}}}printf("Heap %d\n", ca++);int ret = hungary();memcpy(ans, linker, sizeof(ans));if(ret != 2 * n) printf("none\n");else{bool ok = false;for(int i = n; i < 2 * n; i++){g[i][ans[i]] = g[ans[i]][i] = 0;ret = hungary();if(ret == 2 * n) continue;printf("%s(%c,%d)", ok == true? " " : "",'A' + (i - n), ans[i] + 1);ok = true;g[i][ans[i]] = g[ans[i]][i] = 1;}if(!ok) printf("none\n");else printf("\n");}printf("\n");}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/KirinSB/p/10453542.html

總結(jié)

以上是生活随笔為你收集整理的POJ 1486 Sorting Slides（二分图完全匹配必须边）题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。