题目
有(m)条线段，每条线段为([l_i,r_i])，每条线段可以是黑/白色
有些线段已经被染色，有些需要被确定颜色
询问是否存在一种染色方案，使得对于每一个位置(i)，覆盖它的线段黑白个数差的绝对值不超过1
(1 le m le 10^5 , n le 10^9)
题解
-
将每条线段变成([l_i-0.5,r_i+0.5])
-
对于一个合法的方案可以加一些线段使得黑白覆盖的个数相等
-
对(l_i)向(r_i)连一条边，如果把染色看成定向
-
合法的方案满足在相邻两个点的中间划分，正向割边数＝反向隔边数
-
这相当于求一个欧拉回路(暂时不会证)
-
离散化，连边后找到度数为奇数的点补成偶数
-
注意由于一段的-1+1可能是交替的，所以只能对相邻的点补边
-
接着用网络流做混合图的欧拉回路
#include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; const int N=60010; int n,m,cnt,tot,o,S,T,d[N],val[N],cur[N],dis[N],hd[N],id[N],sub[N],tt; map<int,int>mp; map<int,int>::iterator it; struct edge{int u,v,w;}e[N]; struct Edge{int v,nt,f;}E[N<<2]; int get(int x){ int&t=mp[x]; if(t)return t; val[t=++cnt]=x; return t; } void adde(int u,int v,int w){ E[o]=(Edge){v,hd[u],w};hd[u]=o++; E[o]=(Edge){u,hd[v],0};hd[v]=o++; } bool bfs(){ static int head,tail,q[N],vis[N]; for(int i=S;i<=T;++i)vis[i]=0,dis[i]=0; head=tail=0;vis[q[++tail]=S]=1; while(head<tail){ int u=q[++head]; for(int i=hd[u];~i;i=E[i].nt)if(E[i].f&&!vis[E[i].v]){ int v=E[i].v; dis[v]=dis[u]+1;vis[v]=1;q[++tail]=v; if(v==T)return true; } } return false; } int dfs(int u,int F){ if(u==T||!F)return F; int flow=0,f; for(int i=cur[u];~i;i=E[i].nt){ int v=E[cur[u]=i].v; if(dis[v]==dis[u]+1 && (f=dfs(v,min(E[i].f,F)))){ flow+=f,F-=f; E[i].f-=f,E[i^1].f+=f; if(!F)break; } } if(!flow)dis[u]=0; return flow; } int dinic(){ int flow=0; while(bfs()){ for(int i=S;i<=T;++i)cur[i]=hd[i]; flow+=dfs(S,inf); } return flow; } int main(){ freopen("wait.in","r",stdin); freopen("wait.out","w",stdout); scanf("%d%d",&m,&n); for(int i=1,u,v,w;i<=m;++i){ scanf("%d%d%d",&u,&v,&w);v++; sub[++tt]=u;sub[++tt]=v; u=get(u),v=get(v);id[i]=-1; if(w==1)d[v]++,d[u]--; else d[u]++,d[v]--; e[++tot]=(edge){u,v,w}; } sort(sub+1,sub+tt+1); for(int i=1;i<=tt;i+=2){ if(sub[i]==sub[i+1])continue; int u=get(sub[i]),v=get(sub[i+1]); d[u]++,d[v]--; e[++tot]=(edge){u,v,-1}; id[tot]=-1; } /*int lst=0,now=0; for(it=mp.begin();it!=mp.end();++it){ int i=(*it).second; if(!(d[i]&1))continue; if(!lst){lst=i;continue;}else now=i; d[lst]++,d[now]--; e[++tot]=(edge){lst,now,-1}; id[tot]=-1;lst=0; }*/ S=0;T=cnt+1;for(int i=S;i<=T;++i)hd[i]=-1; //cout<<S<<" "<<T<<endl; int sum=0; for(int i=1;i<=cnt;++i)if(d[i]>0)adde(S,i,d[i]/2),sum+=d[i]/2;else adde(i,T,-d[i]/2); for(int i=1;i<=tot;++i)if(!~e[i].w){ e[i].w=0;id[i]=o; adde(e[i].u,e[i].v,1); }// //cout<<o<<endl; if(dinic()!=sum){puts("-1");return 0;} for(int i=1;i<=tot;++i)if(~id[i]&&!E[id[i]].f)e[i].w^=1; /*{ for(int i=1;i<=tot;++i)printf("%d %d %d ",e[i].u,e[i].v,e[i].w); }*/ for(int i=1;i<=m;++i)printf("%d ",e[i].w); return 0; }