[codevs 1232] 飛行員配對方案問題

題解：

做法一：二分圖最大匹配。 做法二：用網絡流求解二分圖最大匹配...
但是都卡在輸出路徑上面。。。糾結要不要直接交數據，反正我有。。。

代碼（未AC）：

#include<cstdio> #include<cstring> using namespace std;const int maxn = 100 + 10;int x[maxn], y[maxn], m, n; bool vis[maxn], g[maxn][maxn];int dfs(int u) {for(int v = n; v >= 1; v--)if(g[u][v] && !vis[v]) {vis[v] = true;if(y[v] == -1 || dfs(y[v])) {x[u] = v;y[v] = u;return 1;}}return 0; }int main() {int u, v, ans = 0;scanf("%d%d", &m, &n);while(scanf("%d%d",&u,&v), u != -1 && v != -1)g[u][v] = g[v][u] = true;memset(x, -1, sizeof(x));memset(y, -1, sizeof(y));for(int i = 1; i <= m; i++) {memset(vis, 0, sizeof(vis));ans += dfs(i);}if(ans) {printf("%d\n", ans);for(int i = 1; i <= m; i++) if(x[i] > 0) printf("%d %d\n", i, x[i]);}else printf("No Solution!"); }

總結

以上是生活随笔為你收集整理的[codevs 1232] 飞行员配对方案问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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