題意：

　　只不過是hdu3081多加了k種選擇

　　想一下，最多能玩x輪，是不是就是每個女生能最多選x個男生

　　現在題中的每個女生比3081多了k中選擇 ? 那就把女生拆點 ?i ?i‘ ?

　　i --> i' 連一條權值為K的邊 ?如果男女無爭吵 連上i --> 男 ?權值為1?

　　有爭吵 連上i' --> 男 權值為1

　　

#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <cctype> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <bitset> #define rap(i, a, n) for(int i=a; i<=n; i++) #define rep(i, a, n) for(int i=a; i<n; i++) #define lap(i, a, n) for(int i=n; i>=a; i--) #define lep(i, a, n) for(int i=n; i>a; i--) #define rd(a) scanf("%d", &a) #define rlld(a) scanf("%lld", &a) #define rc(a) scanf("%c", &a) #define rs(a) scanf("%s", a) #define pd(a) printf("%d\n", a); #define plld(a) printf("%lld\n", a); #define pc(a) printf("%c\n", a); #define ps(a) printf("%s\n", a); #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 100100, INF = 0x7fffffff, LL_INF = 0x7fffffffffffffff; int n, m, z, s, t, cnt, p; int f[maxn], re[300][300]; int d[maxn], cur[maxn], head[maxn]; struct node {int u, v, c, next; }Node[maxn << 1];void add_(int u, int v, int c) {Node[cnt].u = u;Node[cnt].v = v;Node[cnt].c = c;Node[cnt].next = head[u];head[u] = cnt++; }void add(int u, int v, int c) {add_(u, v, c);add_(v, u, 0); }bool bfs() {queue<int> Q;mem(d, 0);Q.push(s);d[s] = 1;while(!Q.empty()){int u = Q.front(); Q.pop();for(int i = head[u]; i != -1; i = Node[i].next){node e = Node[i];if(!d[e.v] && e.c > 0){d[e.v] = d[u] + 1;Q.push(e.v);if(e.v == t) return 1;}}}return d[t] != 0; }int dfs(int u, int cap) {int ret = 0;if(u == t || cap == 0)return cap;for(int &i = cur[u]; i != -1; i = Node[i].next){node e = Node[i];if(d[e.v] == d[u] + 1 && e.c > 0){int V = dfs(e.v, min(cap, e.c));Node[i].c -= V;Node[i ^ 1].c += V;ret += V;cap -= V;if(cap == 0) break;}}if(cap > 0) d[u] = -1;return ret; }int Dinic() {int ans = 0;while(bfs()){memcpy(cur, head, sizeof(head));ans += dfs(s, INF);}return ans; }int find(int x) {return f[x] == x ? x : (f[x] = find(f[x])); }void build(int mid) {for(int i = 1; i <= n; i++){add(s, i, mid);add(n + i, t, mid);add(i, n * 2 + i, p);}for(int i = 1; i <= n; i++)for(int k = n + 1; k <= n * 2; k++){if(re[i][k]) add(i, k, 1);else add(n * 2 + i, k, 1);} }void init() {for(int i = 1; i < maxn; i++) f[i] = i;mem(re, 0);mem(head, -1);cnt = 0; }int main() {int T;rd(T);while(T--){init();int a, b;rd(n), rd(m), rd(p), rd(z);s = 0, t = n * 3 + 1;for(int i = 0; i < m; i++){rd(a), rd(b);b += n;re[a][b] = re[b][a] = 1;}for(int i = 0; i < z; i++){rd(a), rd(b);int r = find(a);int l = find(b);if(r != l) f[l] = r;}for(int i = 1; i <= n; i++){for(int j = i + 1; j <= n; j++){if(find(i) == find(j))for(int k = n + 1; k <= n * 2; k++)re[i][k] = re[j][k] = (re[i][k] || re[j][k]);}}int x = 0, y = 300;while(x <= y){mem(head, -1);cnt = 0;int mid = x + (y - x) / 2;build(mid);if(Dinic() == mid * n) x = mid + 1;else y = mid - 1;}pd(y);}return 0; }

?

轉載于:https://www.cnblogs.com/WTSRUVF/p/9837187.html

總結

以上是生活随笔為你收集整理的Marriage Match III HDU - 3277（二分权值 + 拆点 建边）的全部內容，希望文章能夠幫你解決所遇到的問題。

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