題目

題目鏈接

題意

告訴了n名球員的交換關系，你現在擁有k名球員，你想要其他k名球員(有的在自己隊里)。

輸出一種交換方案。

題解

第一步、求閉包。

• 我們需要在原來的交換矩陣上跑可達閉包，即G[i][j]G[i][j]的含義是jj是否能通過ii的一些交換得到，例如用ii交換aa,再用aa交換bb,再用bb來交換jj。預處理閉包的時間復雜度是O(n3)O(n3)。

第二步、建立二分圖。

• 先預處理出將同時存在與現在隊伍里，和目標隊伍里的球員，這類球員不將其加入二分圖中去。
• 二分圖的左半邊是只出現在現在隊伍里的球員，二分圖的右邊是只出現在目標隊伍里的球員。
• 凡是現在隊伍的球員aa能夠換成目標隊伍里的球員bb的，就在(a,b)(a,b)之間鏈接一條邊。
• 然后跑一個二分圖匹配。（(a,b)(a,b)匹配的含義就是可以把我隊的aa換成目標隊伍里的bb，并且不影響其他任何球員的歸屬。）

第三步、無解判定。

• 當且僅當我隊伍中所有加入二分圖的球員都匹配上了，說明有解，其他情況無解。

第四步、輸出方案。

注意，大寫字母代表這個球員當前屬于我隊。

• 我們遍歷二分圖中所有的匹配(A,b)(A,b)，然后從原矩陣任意找一條從aa到bb的路徑，例如A?>c?>d?>E?>f?>bA?>c?>d?>E?>f?>b。
  那么我們輸出方案如下：E?>f，f?>b，A?>c，c?>d，d?>EE?>f，f?>b，A?>c，c?>d，d?>E
  然后再把b設置為我隊，把A設置為非我隊。
  這樣輸出方案保證了把 A 換成 b 的同時，其他的球員的歸屬沒有發生改變。

• 輸出方案的算法：從后往前依次找到屬于當前位置的節點，并把后面的箭頭依次輸出即可。例如先找到了EE輸出E?>f，f?>bE?>f，f?>b ，又找到了AA，輸出A?>c，c?>d，d?>EA?>c，c?>d，d?>E。

第五步、細節。

• 如何尋找從AA到bb的一條路徑呢。
  使用dfs方法，但要注意經過的點打上標記vis[i] = 1，但是，在返回的時候不要將標記取消！在返回的時候不要將標記取消！在返回的時候不要將標記取消！重要的話說三遍，因為我們只要找到一條路徑就好了，如果在返回過程中將標記取消的話，時間復雜度會爆掉。

證明：不取消標記可以找到一條路徑。

如果通過某條路徑走到vv節點而未能從vv節點走到目標點的話，通過其他路徑走到vv<script type="math/tex" id="MathJax-Element-40">v</script>點也不會走到目標點，這是很顯然的。因此，只要被訪問過的點，而沒有走到終點，我們就無需再次訪問了。

代碼

#include <string.h> #include <vector> #include <queue> #include <iostream> #include <cstdio> using namespace std; typedef std::vector<int>::iterator iterator_t; struct Edge {int from, to; }; #define max_nodes 307 std::vector<Edge> edges; std::vector<int> G[700]; int num_nodes; int num_edges; int num_left, num_right;int match[700]; bool check[700];inline void insert(int lefti, int righti){G[lefti].push_back(edges.size());edges.push_back((Edge){lefti, num_left + righti});G[num_left + righti].push_back(edges.size());edges.push_back((Edge){num_left + righti, lefti}); }bool dfs(int u){for(iterator_t i = G[u].begin(); i != G[u].end(); ++i){int v = edges[*i].to;if(check[v]) continue;check[v] = true;if((match[v] == -1) || dfs(match[v])){match[u] = v;match[v] = u;return true;}}return false; }int hungarian(void){int ans = 0;memset(match, -1, sizeof(match));for(int i = 0; i < num_left; i++){if(match[i] != -1) continue;memset(check, 0, sizeof(bool) * num_nodes);if(dfs(i)) ans++;}return ans; } int MG2[max_nodes][max_nodes]; int n,k; int wanted[max_nodes]; int myteam[max_nodes]; int vis[max_nodes]; int vv[max_nodes]; typedef pair<int,int> pii; vector<pii> fans; vector<int> vG[max_nodes]; pii ps[max_nodes]; int pcnt = 0; int main(){scanf("%d%d",&n,&k);for(int i = 0;i < k;++i){int tmp;scanf("%d",&tmp);myteam[tmp] = 1;}for(int i = 0;i < k;++i){int tmp;scanf("%d",&tmp);wanted[tmp] = 1;}for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j){char c;scanf(" %c",&c);MG2[i][j] = c == '1';if(c == '1') vG[i].push_back(j);}//floydfor(int k = 1;k <= n;++k)for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)MG2[i][j] |= MG2[i][k]&MG2[k][j];int cnt = k;for(int i = 1;i <= n;++i)if(myteam[i] && wanted[i])vis[i] = 1,cnt--;num_nodes = 2*n;num_right = num_left = n;for(int i = 1;i <= n;++i)if(!vis[i] && myteam[i])for(int j = 1;j <= n;++j)if(!vis[j] && wanted[j] && MG2[i][j]){insert(i-1,j-1);}int ans = hungarian();if(ans != cnt)return 0*puts("NO");int dfs2(int,int);for(int i = 1;i <= n;++i){if(wanted[i]){memset(vv,0,sizeof(vv));int from = match[i-1+n]+1;int to = i;if(myteam[to]) continue;vv[from] = 1 ;dfs2(from,to);//vv[from] = 0;myteam[from] = 0;myteam[to] = 1;}}puts("YES");printf("%d\n",fans.size());for(auto p : fans)printf("%d %d\n",p.first,p.second);return 0; } int dfs2(int s,int t){if(s == t)return 1;for(auto i : vG[s]){if(!vv[i]){vv[i] = 1;int r = dfs2(i,t);//vv[i] = 0;if(r){ps[pcnt++] = make_pair(s,i);if(myteam[s]){while(pcnt--)fans.push_back(ps[pcnt]);pcnt = 0;}return 1;}}}return 0; }

總結

以上是生活随笔為你收集整理的codeforces gym-101755 D-Transfer Window 二分图匹配、递归的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。