最大值最小, 是二分
转化为判定问题: 给定一个混合图, 问是否存在欧拉回路
首先, 有向图存在欧拉回路的充要条件是每个点的入度等于出度, 现在我们有一个混合图, 我们要做的就是给其中的无向边定向, 使得它变成有向图之后存在欧拉回路
记点 $x$ 的入度为 $in_x$, 出度为 $out_x$, 我们的目标是使得每个点 $x$ 满足 $in_x-out_x=0$
先随便给每条无向边定向, 这样不一定满足要求, 所以我们必须让某些边反向, 反向 $a\rightarrow b$ 会让 $in_a-out_a$ 增加 $2$, 让 $in_b-out_b$ 减少 $2$, 所以如果存在 $in_x-out_x\equiv1(\text{mod}2)$ 那么无解
为了决定是否反向某些无向边, 我们这样建图:
对于 $in_x\lt out_x$ 的 $x$, 连边 $x\rightarrow T$, 容量为 $\dfrac{out_x-in_x}2$
对于 $in_x\gt out_x$ 的 $x$, 连边 $S\rightarrow x$, 容量为 $\dfrac{in_x-out_x}2$
对于一条无向边, 如果一开始硬点它的方向为 $x\rightarrow y$, 那么连边 $y\rightarrow x$, 权值为 $1$
这样建图跑最大流, 每流过一条原图中的无向边就相当于将它反向 (这条无向边的两个端点的流量之和就是 $\left|in_x-out_x\right|$ 的改变量), 跑最大流是因为我们想要尽可能地缩小 $in_x$ 和 $out_x$ 的差距, 如果满流, 自然就存在欧拉回路了
- #include<stdio.h>
- #include<string.h>
- const int inf=2147483647;
- int abs(int x){return x>0?x:-x;}
- int min(int a,int b){return a<b?a:b;}
- int h[1010],cur[1010],nex[10010],to[10010],cap[10010],dis[1010],q[10010],M,S,T;
- void add(int a,int b,int c){
- M++;
- to[M]=b;
- cap[M]=c;
- nex[M]=h[a];
- h[a]=M;
- M++;
- to[M]=a;
- cap[M]=0;
- nex[M]=h[b];
- h[b]=M;
- }
- bool bfs(){
- int head,tail,x,i;
- memset(dis,-1,sizeof(dis));
- head=tail=1;
- q[1]=S;
- dis[S]=0;
- while(head<=tail){
- x=q[head];
- head++;
- for(i=h[x];i;i=nex[i]){
- if(cap[i]&&dis[to[i]]==-1){
- dis[to[i]]=dis[x]+1;
- if(to[i]==T)return 1;
- tail++;
- q[tail]=to[i];
- }
- }
- }
- return 0;
- }
- int dfs(int x,int flow){
- if(x==T)return flow;
- int i,f;
- for(i=cur[x];i;i=nex[i]){
- if(cap[i]&&dis[to[i]]==dis[x]+1){
- f=dfs(to[i],min(flow,cap[i]));
- if(f){
- cap[i]-=f;
- cap[i^1]+=f;
- if(cap[i])cur[x]=i;
- return f;
- }
- }
- }
- dis[x]=-1;
- return 0;
- }
- int dicnic(){
- int ans=0,tmp;
- while(bfs()){
- memcpy(cur,h,sizeof(h));
- while(tmp=dfs(S,inf))ans+=tmp;
- }
- return ans;
- }
- int n,m,in[1010],ou[1010];
- struct edge{
- int x,y,a,b;
- }e[2010];
- bool check(int lim){
- int i,s;
- memset(h,0,sizeof(h));
- memset(in,0,sizeof(in));
- memset(ou,0,sizeof(ou));
- M=1;
- for(i=1;i<=m;i++){
- if(e[i].a<=lim&&e[i].b<=lim){
- add(e[i].y,e[i].x,1);
- ou[e[i].x]++;
- in[e[i].y]++;
- }else if(e[i].a<=lim){
- ou[e[i].x]++;
- in[e[i].y]++;
- }else if(e[i].b<=lim){
- ou[e[i].y]++;
- in[e[i].x]++;
- }else
- return 0;
- }
- s=0;
- for(i=1;i<=n;i++){
- if(abs(in[i]-ou[i])&1)return 0;
- if(in[i]<ou[i])add(i,T,(ou[i]-in[i])>>1);
- if(in[i]>ou[i]){
- add(S,i,(in[i]-ou[i])>>1);
- s+=(in[i]-ou[i])>>1;
- }
- }
- return s==dicnic();
- }
- int main(){
- int i,l,r,mid,ans;
- scanf("%d%d",&n,&m);
- for(i=1;i<=m;i++)scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].a,&e[i].b);
- S=n+1;
- T=n+2;
- ans=-1;
- l=0;
- r=1000;
- while(l<=r){
- mid=(l+r)>>1;
- if(check(mid)){
- ans=mid;
- r=mid-1;
- }else
- l=mid+1;
- }
- if(ans==-1)
- puts("NIE");
- else
- printf("%d",ans);
- }
- [BZOJ2095]Bridges
来源: http://www.bubuko.com/infodetail-2570739.html