~bzoj|【bzoj 2095】Bridges（二分+混合图的欧拉回路）
传送门biu~
求混合图的欧拉回路的方法：
1.对于所有无向边任意定向。
2.计算出所有点的入度和出度，如果有点的入度与出度的奇偶性不同，那么无解。
3.将所有 入度>出度 的点向汇点连一条容量为 (入度?出度)/2 的弧，源点向所有 出度>入度 的点连一条容量为 (出度?入度)/2 的弧，再对于原图中所有的定向为a->b无向边连一条从a到b容量为1的弧。
4.跑最大流，如果正好能使所有从源点出来的弧满流，则有解。
5.把在网络流中那些因为原图无向边而建的流量为1的边中经过流量的边反向，就形成了一个能跑出欧拉回路的有向图。求方案时，用有向图求欧拉回路的方法求解即可。
解析：首先只有当所有点的“入度=出度”时，这张图才能有欧拉回路。所以我们的目标是调整“无向边”的方向使得每个点的入度等于出度。考虑我们刚才所进行的网络流建图，从源到汇的一条增广路中经过的那些“原来是无向边而产生的边”，相当于把它们全部进行反向。这样中间经过的那些点出度入度不变，只有一开始的点入度+1，出度-1、最后的点入度-1，出度+1。所以当源点到一个点的那条边满流时，就意味着这个点的出度已经等于入度了，自调整的过程已经完成。而当全部的点全部完成这一事件时，就说明已经能找到一条欧拉回路了。
【~bzoj|【bzoj 2095】Bridges（二分+混合图的欧拉回路）】对于本题，首先应该二分求出经过的欧拉回路上承受的风力的最大值。在这个最大值的约束下，原来的某些无向边因为某个方向的风力过大，只能从另一个方向通过。即无向边到有向边的改变。在最大值的限制下，原图变成了一个混合图，用上面说到的方法就可以判断是否有欧拉回路了。
#include
#define N 1050
#define M 8050
#define inf 1000000000
using namespace std;
struct Edge{int u,v,w1,w2;
}e[2005];
int n,m,S,T,tot,ans,head[N],fir[N],dep[N],degree[N],nex[M],to[M],cap[M],tp;
queueq;
inline void add(int x,int y,int c){
nex[++tp]=head[x];
head[x]=tp;
to[tp]=y;
cap[tp]=c;
}
inline void Insert(int x,int y,int c){add(x,y,c);
add(y,x,0);
}
inline int bfs(){
memset(dep,0,sizeof(dep));
q.push(S);
dep[S]=1;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];
i;
i=nex[i]){
if(!dep[to[i]] && cap[i]){
dep[to[i]]=dep[x]+1;
q.push(to[i]);
}
}
}
return dep[T];
}
int dfs(int x,int now){
if(!now || x==T)return now;
int c=0;
for(int &i=fir[x];
i;
i=nex[i]){
if(dep[to[i]]==dep[x]+1 && cap[i]){
int f=dfs(to[i],min(now,cap[i]));
c+=f;
now-=f;
cap[i]-=f;
cap[i^1]+=f;
if(!now)break;
}
}
return c;
}
inline int Dinic(){
int c=0;
while(bfs()){
for(int i=S;
i<=T;
++i)fir[i]=head[i];
c+=dfs(S,inf);
}
return c;
}
inline bool check(int x){
memset(head,0,sizeof head);
tp=1;
for(int i=1;
i<=m;
++i){
if(e[i].w1>x)return false;
if(e[i].w2<=x)Insert(e[i].u,e[i].v,1);
}
for(int i=1;
i<=n;
++i){
if(degree[i]>0)Insert(S,i,degree[i]/2);
if(degree[i]<0)Insert(i,T,-degree[i]/2);
}
return (Dinic()*2==tot);
}
int main(){
scanf("%d%d",&n,&m);
S=0,T=n+1;
for(int i=1;
i<=m;
++i){
scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].w1,&e[i].w2);
if(e[i].w1>e[i].w2) swap(e[i].u,e[i].v),swap(e[i].w1,e[i].w2);
++degree[e[i].u],--degree[e[i].v];
}
for(int i=1;
i<=n;
++i){
if(degree[i]&1){
puts("NIE");
return 0;
}
tot+=abs(degree[i])>>1;
}
int l=1,r=1000;
while(l<=r){
int mid=l+r>>1;
if(check(mid))ans=mid,r=mid-1;
elsel=mid+1;
}
printf("%d\n",ans);
return 0;
}
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长