codeforces 1070I 2018-2019 ICPC,NEERC,Southern Subregional Contest Privatization of Roads in Berlan

xiaoxiao2022-07-05  61

题面

题意

给出一张无向图,现在要对上面的边进行染色(可以认为有无数种颜色),并且每种边只能染一种颜色,每种颜色最多只能染两条边,并且与每个点相连的边最多只有k种颜色,请输出一种方案。

做法

首先如果存在一个度数大于 2 k 2k 2k的点,肯定无解,而对于度数小于等于 k k k的点,则无论其周围的边如何染色,都不会超过 k k k个颜色,因此我们只要考虑度数在 k + 1 k+1 k+1 2 k 2k 2k之间的点即可。 可以发现,对于度数为 i ( k < i < = 2 k ) i(k<i<=2k) i(k<i<=2k)的点,在其周围的 i i i条边中必然有 i − k i-k ik对边的颜色相同,我们称这些边为特殊边,则特殊边总是成对出现,且每对特殊边只能出现在一个点的旁边,因此这题可以转化为一个匹配问题,一个度数为 i i i点要与 m a x ( 2 ∗ ( i − k ) , 0 ) max(2*(i-k),0) max(2(ik),0)条与它相连的边匹配,可以用最大流求解,判断最大流是否与源点的出度相等即可。

代码

#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define N 1210 #define M 100100 using namespace std; int T,m,n,k,s,t,bb,first[N],ds[N],cur[N],deep[N],a[N],b[N],an[N],ss,ts,ans,tt; struct Bn { int to,next,quan; }bn[M]; vector<int>son[N]; queue<int>que; inline void add(int u,int v,int w) { bb++; bn[bb].to=v; bn[bb].next=first[u]; bn[bb].quan=w; first[u]=bb; } inline void ad(int u,int v,int w) { add(u,v,w); add(v,u,0); } inline bool bfs() { int p,q; memset(deep,0,sizeof(deep)); deep[s]=1; que.push(s); for(;!que.empty();) { q=que.front(); que.pop(); for(p=first[q];p!=-1;p=bn[p].next) { if(deep[bn[p].to] || !bn[p].quan) continue; deep[bn[p].to]=deep[q]+1; que.push(bn[p].to); } } return deep[t]; } int dfs(int now,int mn) { if(now==t) return mn; int res; for(int &p=cur[now];p!=-1;p=bn[p].next) { if(!bn[p].quan || deep[bn[p].to]!=deep[now]+1) continue; res=dfs(bn[p].to,min(bn[p].quan,mn)); if(res) { bn[p].quan-=res; bn[p^1].quan+=res; return res; } } return 0; } int main() { int i,j,p,q,o,tmp; cin>>T; while(T--) { bb=1,ss=ts=0; memset(ds,0,sizeof(ds)); memset(first,-1,sizeof(first)); memset(an,0,sizeof(an)); scanf("%d%d%d",&n,&m,&k); s=0,t=m+n+1; for(i=1;i<=m;i++) { scanf("%d%d",&p,&q); ad(p+m,i,1); ad(q+m,i,1); ds[p]++,ds[q]++; } for(i=1;i<=m;i++) ad(i,t,1),ts++; for(i=1;i<=n;i++) { if(ds[i]>k) ad(s,i+m,(ds[i]-k)*2),ss+=(ds[i]-k)*2; } if(i<=n || ss>ts) { for(i=1;i<=m;i++) printf("0 "); puts(""); continue; } ans=tt=0; for(;bfs();) { for(i=0;i<=t;i++) cur[i]=first[i]; for(p=dfs(s,INF);p;ans+=p,p=dfs(s,INF)); } if(ans<ss) { for(i=1;i<=m;i++) printf("0 "); puts(""); continue; } for(i=1;i<=n;i++) son[i].clear(); for(i=1;i<=m;i++) { for(p=first[i];p!=-1;p=bn[p].next) { if(bn[p].to>m&&bn[p].to<=m+n&&bn[p].quan) { son[bn[p].to-m].push_back(i); break; } } } for(i=1;i<=n;i++) { for(j=0;j<son[i].size();j+=2) { an[son[i][j]]=an[son[i][j+1]]=++tt; } } for(i=1;i<=m;i++) { if(an[i]) printf("%d ",an[i]); else printf("%d ",++tt); } puts(""); } }
转载请注明原文地址: https://www.6miu.com/read-4968444.html

最新回复(0)