?

題目大意：有n個人，兩個人之間有相互的關系，問最大的關系數目。

思路：n-（最大匹配數/2）。因為這里給出的是n個人之間的兩兩關系

?

//看看會不會爆int!數組會不會少了一維！ //取物問題一定要小心先手勝利的條件 #include <bits/stdc++.h> using namespace std; #define LL long long #define ALL(a) a.begin(), a.end() #define pb push_back #define mk make_pair #define fi first #define se second #define haha; printf("haha\n"); const int maxn = 500 + 5; int myleft[maxn]; int T[maxn]; bool vis[maxn][maxn]; vector<int> G[maxn]; int n;bool match(int u){int len = G[u].size();for (int i = 0; i < len; i++){int v = G[u][i];if (!T[v]){T[v] = true;if (myleft[v] == -1 || match(myleft[v])){myleft[v] = u;return true;}}}return false; }int main(){while (scanf("%d", &n) == 1){for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){vis[i][j] = false;}G[i].clear();}for (int i = 1; i <= n; i++){int k, u;scanf("%d: (%d)", &u, &k);for (int i = 0; i < k; i++){int v; scanf("%d", &v);G[u].push_back(v);vis[u][v] = true;}}memset(myleft, -1, sizeof(myleft));int ans = 0;for (int i = 0; i < n; i++){memset(T, 0, sizeof(T));ans += match(i);}for (int i = 0; i < n; i++){printf("left[%d] = %d\n", i, myleft[i]);}printf("%d\n", n - ans / 2);}return 0; } View Code

?

轉載于:https://www.cnblogs.com/heimao5027/p/5890253.html

總結

以上是生活随笔為你收集整理的最大独立集 HDU 1068的全部內容，希望文章能夠幫你解決所遇到的問題。

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