My|2095: [Poi2010]Bridges 二分+混合图欧拉回路（网络流）
【My|2095: [Poi2010]Bridges 二分+混合图欧拉回路（网络流）】好厉害的题啊QAQ，并不会做。
最大值最小想到是二分，然后就是一个混合图欧拉回路的问题。
混合图欧拉回路问题的解决：
我们首先想到有向图的欧拉回路，需满足的条件是每个点的入度等于出度。那么对于一个混合图来说，可能有的点入度>出度，而有的点入度<出度，对于这种情况，我们可能可以通过改变一条边的方向来使这两个点都满足入度等于出度的条件。
那么我们可以首先给这个图的无向边随便定一个方向，计算出每个点的入度和出度。现在的问题变成了：该改变那些边的方向来使得存在欧拉回路？
这个问题可以通过网络流来解决，首先对于有向边我们可以忽略，因为它对于点的入度和出度的贡献是固定的，不会改变。然后对于一条无向边(u,v)，若我们假定初始方向为u->v,那么我们在网络中建立(v,u,1)的边，代表我们可以走1个流量来“反悔”，假设|入度-出度|=a，然后对于入度>出度的点x，假设|入度-出度|=a，建立(S,x,a>>1),对于入度<出度的点，我们建立(x,T,a>>1)。然后跑网络流，自动分配流量，如果流入的=流出的，代表所有点的入度和出度都相等了，此时这个图存在欧拉回路，否则就不存在欧拉回路。
还有，如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。
至于本题，加一个二分答案然后判定就好了。
#include
#include
#include
#define inf 1000000007
using namespace std;
int n,m,l=inf,r,R,tot,cnt;
int v[2005],u[2005],c[2005],d[2005];
int next[1000005],list[1000005],key[1000005];
int head[1005],dis[1005],q[1005],ind[1005];
inline int read()
{
int a=0,f=1;
char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;
c=getchar();
}
while (c>='0'&&c<='9') {a=a*10+c-'0';
c=getchar();
}
return a*f;
}
inline void insert(int x,int y,int z)
{
next[++cnt]=head[x];
head[x]=cnt;
list[cnt]=y;
key[cnt]=z;
}
inline void build(int mid)
{
memset(head,0,sizeof(head));
memset(ind,0,sizeof(ind));
cnt=1;
tot=0;
for (int i=1;
i<=m;
i++)
{
if (c[i]<=mid) ind[u[i]]--,ind[v[i]]++;
if (d[i]<=mid) insert(v[i],u[i],1),insert(u[i],v[i],0);
}
for (int i=1;
i<=n;
i++)
if (ind[i]>0) tot+=ind[i]/2,insert(0,i,ind[i]/2),insert(i,0,0);
else insert(i,n+1,-ind[i]/2),insert(n+1,i,0);
}
inline bool BFS()
{
memset(dis,-1,sizeof(dis));
int t=0,w=1,x;
q[1]=0;
dis[0]=1;
while (t!=w)
{
x=q[++t];
for (int i=head[x];
i;
i=next[i])
if (dis[list[i]]==-1&&key[i])
dis[list[i]]=dis[x]+1,q[++w]=list[i];
}
return dis[n+1]!=-1;
}
int find(int x,int flow)
{
if (x==n+1) return flow;
int w,used=0;
for (int i=head[x];
i;
i=next[i])
if (dis[list[i]]==dis[x]+1&&key[i])
{
w=find(list[i],min(flow-used,key[i]));
key[i]-=w;
key[i^1]+=w;
used+=w;
if (used==flow) return used;
}
if (!used) dis[x]=-1;
return used;
}
inline int dinic()
{
int tmp=0;
for (int i=1;
i<=n;
i++) if (ind[i]&1) return -1;
while (BFS()) tmp+=find(0,inf);
return tmp;
}
int main()
{
n=read();
m=read();
for (int i=1;
i<=m;
i++)
{
u[i]=read();
v[i]=read();
c[i]=read();
d[i]=read();
if (c[i]>d[i]) swap(c[i],d[i]),swap(u[i],v[i]);
l=min(l,c[i]);
r=max(r,d[i]);
}
R=r;
while (l<=r)
{
int mid=l+r>>1;
build(mid);
if (dinic()==tot) r=mid-1;
else l=mid+1;
}
if (l==R+1) puts("NIE");
else cout << l << endl;
return 0;
} 推荐阅读
- ~bzoj|【bzoj 2095】Bridges（二分+混合图的欧拉回路）
- HDOJ-2095|HDOJ-2095 Find your present (2) / NYOJ-528 找球号（三）
- BZOJ P2091[Poi2010]The Minima Game
- 二分答案|【BZOJ2095/POI2010】Bridges
- BZOJ|[BZOJ]2095 二分答案 + 混合图欧拉回路判定
- POI|图论欧拉回路初步 & BZOJ2095 POI2010 Bridges