题意:
二分图 有 k 条边, 我们去选择其中的几条 每选中一条那么此条边的 u 和 v 的度数就 + 1, 最后使得所有点的度数都在 [l, r] 这个区间内 , 这就相当于 边的入度 + 1, 出度 + 1, 最后使流量平衡
解析:
这是一个无源汇有上下界可行流
先添加源点和汇点 超级源超级汇 跑边 dinic 当前弧优化的板子 就好了... 看了一发蔡队的代码, 学到了好多新知识(逃)...
- #include <bits/stdc++.h>
- #define mem(a, b) memset(a, b, sizeof(a))
- #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
- using namespace std;
- const int maxn = 100100, INF = 0x7fffffff;
- int d[maxn], head[maxn], in[maxn], low[maxn], id[maxn], cur[maxn];
- int n, m, s, t, ans_flow, ans, cnt, k, ss, tt;
- 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);
- }
- int 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[e.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[e.u] + 1 && e.c> 0)
- {
- int V = dfs(e.v, min(cap, e.c));
- if(V> 0)
- {
- 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 u)
- {
- int sum_flow = 0;
- while(bfs())
- {
- memcpy(cur, head, sizeof(head));
- sum_flow += dfs(u, INF);
- }
- return sum_flow;
- }
- int main()
- {
- int l, r;
- int kase = 0;
- while(~scanf("%d%d%d", &n, &m, &k))
- {
- ans_flow = 0;
- mem(head, -1);
- mem(in, 0);
- cnt = 0;
- rd(l), rd(r);
- ss = n+m+1, tt = n+m+2;
- s = 0, t = n+m+3;
- int u, v;
- for(int i=0; i<k; i++)
- {
- rd(u), rd(v);
- add(u, n+v, 1);
- }
- for(int i=1; i<=n; i++)
- {
- add(ss, i, r-l);
- add(s, i, l);
- }
- for(int i=1; i<=m; i++)
- {
- add(n+i, tt, r-l);
- add(n+i, t, l);
- }
- add(ss, t, l*n);
- add(s, tt, l*m);
- add(tt, ss, INF);
- ans_flow = l*(n+m);
- int sum_flow = Dinic(s);
- printf("Case %d:", ++kase);
- if(sum_flow == ans_flow)
- puts("Yes");
- else
- puts("No");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2760760.html