Description
小 N 最近在研究 NP 完全问题, 小 O 看小 N 研究得热火朝天, 便给他出了一道这样的题目:
有 n 个球, 用整数 1 到 n 编号. 还有 m 个筐子, 用整数 1 到 m 编号.
每个筐子最多能装 3 个球.
每个球只能放进特定的筐子中. 具体有 e 个条件, 第 i 个条件用两个整数 vi 和 ui 描述, 表示编号为 vi 的球可以放进编号为 ui 的筐子中.
每个球都必须放进一个筐子中. 如果一个筐子内有不超过 1 个球, 那么我们称这样的筐子为半空的.
求半空的筐子最多有多少个, 以及在最优方案中, 每个球分别放在哪个筐子中.
小 N 看到题目后瞬间没了思路, 站在旁边看热闹的小 I 嘿嘿一笑:"水题!"
然后三言两语道出了一个多项式算法.
小 N 瞬间就惊呆了, 三秒钟后他回过神来一拍桌子:
"不对! 这个问题显然是 NP 完全问题, 你算法肯定有错!"
小 I 浅笑:"所以, 等我领图灵奖吧!"
小 O 只会出题不会做题, 所以找到了你 -- 请你对这个问题进行探究, 并写一个程序解决此题.
Input
第一行包含 1 个正整数 T, 表示有 T 组数据.
对于每组数据, 第一行包含 3 个正整数 n,m,e, 表示球的个数, 筐子的个数和条件的个数.
接下来 e 行, 每行包含 2 个整数 vi,ui, 表示编号为 vi 的球可以放进编号为 ui 的筐子.
Output
对于每组数据, 先输出一行, 包含一个整数, 表示半空的筐子最多有多少个.
- Sample Input
- 1
- 4 3 6
- 1 1
- 2 1
- 2 2
- 3 2
- 3 3
- 4 3
- Sample Output
- 2
- HINT
对于所有数据, T5,1n3m. 保证 1vin,1uim, 且不会出现重复的条件.
保证至少有一种合法方案, 使得每个球都放进了筐子, 且每个筐子内球的个数不超过 3.
M<=100
Solution
这道题是难在构造还是难在带花树我也实在是没办法知道了....
首先我们初看这个题的时候可能压根没有头绪, 毕竟, 题目都已经在误导你了, 还给你整个了没法证明的问题出来...
换一个角度来看, 我们要使一个箱子是半空的, 那么他要么只装了一个球, 要么没有装球. 联系一个箱子最多只能装三个球这个条件, 我们可以把一个箱子看成是这个样子的:
没有图.
然后我们发现如果被匹配走了超过一个点, 这个环内部就不能够构成匹配了.
好了, 那么我们就可以得知, 我们把一个箱子拆成三个点, 然后这三个点互相连边, 就可形成一个奇环, 然后每个球往这三个点连边, 然后设置超级源汇, 跑网络流即可, 然后来一棵带花树分分钟就可以秒杀这个题.
- Code
- #pragma comment(linker, "/STACK:1024000000,1024000000")
- #include <iostream>
- #include <cstdlib>
- #include <cmath>
- #include <string>
- #include <cstring>
- #include <cstdio>
- #include <algorithm>
- #include <queue>
- #include <set>
- #include <map>
- #define re register
- #define max(a,b) ((a)>(b)?(a):(b))
- #define min(a,b) ((a)<(b)?(a):(b))
- #define MAXN 605
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- #define ms(arr) memset(arr, 0, sizeof(arr))
- const int inf = 0x3f3f3f3f;
- int f[MAXN],head[MAXN],next[MAXN],match[MAXN],vis[MAXN],mark[MAXN],num,t;
- int n,m,E,sum,tot,cnt;
- struct po
- {
- int to,nxt;
- }edge[MAXN*MAXN];
- queue<int> q;
- inline int read()
- {
- int x=0,c=1;
- char ch=' ';
- while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
- while(ch=='-') c*=-1,ch=getchar();
- while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
- return x*c;
- }
- int find(int x)
- {
- return f[x]==x?f[x]:f[x]=find(f[x]);
- }
- inline void add_edge(int from,int to)
- {
- edge[++num].nxt=head[from];
- edge[num].to=to;
- head[from]=num;
- }
- inline void add(int from,int to)
- {
- add_edge(from,to);
- add_edge(to,from);
- }
- inline int lca(int x,int y)
- {
- t++;
- while(1){
- if(x){
- x=find(x);
- if(vis[x]==t) return x;
- vis[x]=t;
- if(match[x]) x=next[match[x]];
- else x=0;
- }
- swap(x,y);
- }
- }
- inline void flower(int a,int p)
- {
- while(a!=p){
- int b=match[a],c=next[b];
- if(find(c)!=p) next[c]=b;
- if(mark[b]==2) q.push(b),mark[b]=1;
- if(mark[c]==2) q.push(c),mark[c]=1;
- f[find(a)]=find(b);f[find(b)]=find(c);
- a=c;
- }
- }
- inline void work(int s)
- {
- for(re int i=1;i<=sum;i++)
- next[i]=mark[i]=vis[i]=0,f[i]=i;
- while(!q.empty()) q.pop();
- mark[s]=1;q.push(s);
- while(!q.empty()){
- if(match[s]) return;
- int x=q.front();q.pop();
- for(re int i=head[x];i;i=edge[i].nxt){
- int y=edge[i].to;
- if(match[x]==y) continue;
- if(find(x)==find(y)) continue;
- if(mark[y]==2) continue;
- if(mark[y]==1) {
- int r=lca(x,y);
- if(find(x)!=r) next[x]=y;
- if(find(y)!=r) next[y]=x;
- flower(x,r);flower(y,r);
- }
- else if(!match[y]){
- next[y]=x;
- for(re int u=y;u;){
- int v=next[u],w=match[v];
- match[v]=u;match[u]=v;u=w;
- }
- break;
- } else {
- next[y]=x;
- mark[match[y]]=1;
- q.push(match[y]);
- mark[y]=2;
- }
- }
- }
- }
- inline int solve()
- {
- int ans=0;
- for(re int i=1;i<=sum;i++) if(!match[i]) work(i);
- for(re int i=1;i<=sum;i++) if(match[i]) ans++;
- return ans/2;
- }
- int main()
- {
- int T=read();
- while(T--){
- n=read();m=read();E=read();
- sum=n+m*3;num=0;cnt=0;t=0;
- memset(head,0,sizeof(head));
- memset(match,0,sizeof(match));
- for(re int i=1;i<=E;i++){
- int x=read(),y=read();
- add(x,n+y);
- add(x,n+m+y);
- add(x,n+m+m+y);
- }
- for(re int i=1;i<=m;i++){
- add(n+i,n+m+i);
- add(n+i,n+i+m+m);
- add(n+i+m,n+i+m+m);
- }
- printf("%d\n", solve()-n);
- for(re int i=1;i<=n;i++) printf("%d",(match[i]-n-1)%m+1);
- }
- return 0;
- }
[WC2016] 挑战 NPC
来源: http://www.bubuko.com/infodetail-2647028.html