http://poj.org/problem?id=2594
太經(jīng)典了,最小路徑覆蓋之變形!如果題目中有暗示此圖無環(huán)且路徑是單向的話,必然是最小路徑覆蓋無疑!
這個題的題目意思和那個傘兵題差不多,但是傘兵走過的路徑是可以交叉的,
這樣我們先做一個傳遞閉包,然后再連邊做最小路徑覆蓋即可。
Source Code
Problem: 2594 | ? | User: 541780774 |
Memory: 652K | ? | Time: 1110MS |
Language: G++ | ? | Result: Accepted |
Source Code
#include<stdio.h> #include<stdlib.h> #include<string.h> int nx, ny; // X的點(diǎn)數(shù)目、Y的點(diǎn)數(shù)目 int mx[501], my[501]; // X各點(diǎn)的配對對象、Y各點(diǎn)的配對對象 bool vy[501]; // 紀(jì)錄Graph Traversal拜訪過的點(diǎn) bool adj[501][501]; // 精簡過的adjacency matrix // 以DFS建立一棵交錯樹 bool DFS(int x) { for (int y=0; y<ny; ++y) if (adj[x][y] && !vy[y]) { vy[y] = true; // 找到擴(kuò)充路徑 if (my[y] == -1 || DFS(my[y])) { mx[x] = y; my[y] = x; return true; } } return false; } int bipartite_matching() { // 全部的點(diǎn)初始化為未匹配點(diǎn)。 memset(mx, -1, sizeof(mx)); memset(my, -1, sizeof(my)); // 依序把X中的每一個點(diǎn)作為擴(kuò)充路徑的端點(diǎn), // 並嘗試尋找擴(kuò)充路徑。 int c = 0; for (int x=0; x<nx; ++x) // if (mx[x] == -1) // x為未匹配點(diǎn),這行可精簡。 { // 開始Graph Traversal memset(vy, false, sizeof(vy)); if (DFS(x)) c++; } return c; } void Floyd(int n) { int i,j,k; for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) { if(i!=j&&adj[i][k]&&adj[k][j]) adj[i][j]=1; } } main() { int i,a,b,n,m; while(scanf("%d%d",&n,&m),n!=0||m!=0) { memset(adj, 0, sizeof(adj)); for(i=0;i<m;i++) { scanf("%d%d",&a,&b); adj[a-1][b-1]=1; } Floyd(n); nx=ny=n; printf("%d\n",n-bipartite_matching()); } system("pause"); }
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
