1 or 2
题目大意
给一个无向图,给一个长度为n的a数组
问能不能删除一些边以后能不能让每个点的度数为ai
题解
比赛的时候,因为数据水,用网络流,乱水过去了,后来才知道有反例,不能跑网络流。
正解:
建图方式:拆点,把这个点拆成ai个点,如果有一个边x- - - - -y
就在图中新建两个点代表x,y 就把 x拆的点与x相连 y拆的点与y相连,再把x,y相连。
建完图之后,跑一个带花树板子就好了。
如果是完美匹配,那么就yes,否则是no
为什么这样建图是对的呢?
因为建完图之后会发现,随便提溜起来一条边,都可以向两边拆点中匹配一条边,并且只能匹配一次,如果一条边只有一边的度数为1那么另一边一定没有连点,一定匹配不到,那么就是no
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
typedef unsigned long long ull;
typedef set<int>::iterator sit;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){
freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){
freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
a %= mod;ll ans = 1;while(b){
if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
bool operator()(const pii & a, const pii & b){
return a.second > b.second;}};
int lb(int x){
return x & -x;}
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int M = 4e4+2;
const ll mod = 2012;
const int maxn = 555;
int head[maxn];
struct Edge
{
int id,nex;
}edge[maxn * maxn * 2];
int cnt = 0;
void add(int x,int y)
{
edge[cnt].id = y;
edge[cnt].nex = head[x];
head[x] = cnt ++ ;
}
/* 并查集维护 */
int fa[maxn];
int findx(int x)
{
if(fa[x] == x)
return x;
return fa[x] = findx(fa[x]);
}
int link[maxn];// 记录路径
int vis[maxn]; // 标记层数是奇数或偶数
int mate[maxn];// 匹配的点
//queue<int> qq;// bfs找增广路用的队列
int qq[maxn <<2];int hd,tl;
int ss[maxn], tim;
int lca(int x,int y)
{
++tim;
while(ss[x] != tim)
{
if(x)
{
ss[x] = tim;
x = findx(link[mate[x]]);
}
swap(x,y);
}
return x;
}
void flower(int x,int y,int p)
{
while(findx(x) != p)
{
link[x] = y;
y = mate[x];
fa[y] = fa[x] = p;
if(vis[y] == 1)
{
// qq.push(y);
qq[tl++] = y;
vis[y] = 2;
}
x = link[y];
}
}
int pnum;
bool match(int x) // 找增广路 匹配。
{
hd = 0, tl = 0;// 队列的两个指针
for (int i= 1; i <= pnum; i ++ )
{
fa[i] = i;
vis[i] = 0;
}
vis[x] = 2; // 标记为偶数层
qq[tl ++ ] = x;
while(tl > hd)
{
// x = qq.front();qq.pop();
x = qq[hd];
// cout<<x<<endl;
hd ++ ;
for(int i = head[x]; ~i; i = edge[i].nex)
{
int v = edge[i].id;
// cout<<v<<mate[v]<<vis[v]<<endl;
if(vis[v] == 0)// 还没走过
{
vis[v] = 1;
link[v] = x;// 记录路径,是从x转移过来的
if(mate[v] == 0)
{
while(x)
{
x = mate[link[v]];
mate[v] = link[v];
mate[link[v]] = v;
v = x;
}
return true;
}
else
{
// qq.push(mate[v]);
qq[tl++] = mate[v];
vis[mate[v]] = 2;
}
}
else if(vis[v] == 2 && findx(v) != findx(x))
{
int p = lca(x,v);
flower(x,v,p);
flower(v,x,p);
}
}
}
return false;
}
int du[maxn];
vector<int> vv[maxn];
int main()
{
int n,m;
memset(head,-1,sizeof(head));
while(scanf("%d%d",&n,&m)!=EOF)
{
tim = 0;
cnt = 0;
pnum = 0;
for (int i = 1; i <= n; i ++ )
{
scanf("%d",&du[i]);
for (int j = 0; j < du[i]; j ++ )
{
vv[i].pb(++pnum);
}
}
for (int i = 1; i <= m; i ++ )
{
int x,y;
scanf("%d%d",&x,&y);
++pnum;
for (int j = 0; j < vv[x].size(); j ++ )
{
add(pnum,vv[x][j]);
add(vv[x][j],pnum);
// cout<<vv[x][j]<<cnt<<endl;;
}
++pnum;
add(pnum,pnum - 1);
add(pnum - 1,pnum);
// cout<<cnt<<cnt - 1<<endl;
for(int j = 0; j < vv[y].size(); j ++ )
{
add(pnum,vv[y][j]);
add(vv[y][j],pnum);
// cout<<vv[y][j]<<cnt<<endl;
}
}
int f = 1;
for (int i = 1; i <= pnum; i ++ )
{
if(mate[i] == 0 && (!match(i)))
{
f = 0;
break;
}
// cout<<i<<mate[i]<<"111111111111"<<endl;;
}
if(f)
printf("Yes\n");
else
printf("No\n");
for(int i = 1; i<= pnum; i ++ )
{
ss[i] = 0;
link[i] = 0;
vv[i].clear();
head[i] = -1;
mate[i] = 0;
}
}
}
带花树板子,还没有完全懂。。 我好菜。