hdu 3472 HS BDC(混合路的欧拉路径)

这题是混合路的欧拉路径问题。

1.判断图的连通性,若不连通,无解。

2.给无向边任意定向,计算每个结点入度和出度之差deg[i]。deg[i]为奇数的结点个数只能是0个或2个,否则肯定无解。

3.(若存在2个deg[i]为奇数的结点,则在两点连一条流量为1的边,方向任意)设立源点s和汇点t(自己另外定两个点),若某点i入度<出度,连边(s,i,-deg[i]/2),若入度>出度,连边(i,t,deg[i]/2);对于任意定向的无向边(i,j,1)。

5.若从S发出的边全部满流,证明存在欧拉回路(路径),否则不存在。

hdu 3472 HS BDC(混合路的欧拉路径)hdu 3472 HS BDC(混合路的欧拉路径)
view code#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 1<<30;
const int N = 2010;
int _,cas=1, n, fa[30], pre[30], deg[30], s, t, d[30];
int cur[30];
bool vis[30]; struct edge
{
int u, v, cap, next;
edge() {}
edge(int u, int v, int w, int next):u(u),v(v),cap(w),next(next) {}
}e[N<<1];
int ecnt; void addedge(int u, int v, int w)
{
e[ecnt] = edge(u, v, w, pre[u]);
pre[u] = ecnt++;
e[ecnt] = edge(v, u, 0, pre[v]);
pre[v] = ecnt++;
} int find(int x)
{
return x==fa[x]?x:(fa[x]=find(fa[x]));
} void Union(int u, int v)
{
u = find(u), v= find(v);
if(u==v) return ;
fa[u] = v;
} bool is_ok()
{
for(int i=0; i<26; i++) if(vis[i] && find(i)!=find(s)) return false;
int res = 0;
for(int i=0; i<26; i++) if(deg[i]%2){
res++;
if(res==1) s = i;
else t = i;
}
return res==0 || res==2;
} bool BFS()
{
memset(vis, 0, sizeof(vis));
queue<int >q;
q.push(s);
d[s] = 0, vis[s]=1;
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i=pre[u]; ~i; i=e[i].next)
{
int v = e[i].v;
if(!vis[v] && e[i].cap>0)
{
vis[v] = 1;
d[v] = d[u] +1;
q.push(v);
}
}
}
return vis[t];
} int DFS(int u, int c)
{
if(u==t || c==0) return c;
int flow=0, f;
for(int &i=pre[u]; ~i; i=e[i].next)
{
int v = e[i].v;
if(d[v]==d[u]+1 && (f=DFS(v, min(c, e[i].cap)))>0)
{
e[i].cap -= f;
e[i^1].cap += f;
flow += f;
c -= f;
if(c==0) break;
}
}
return flow;
} int Maxflow()
{
int flow = 0;
while(BFS())
{
memcpy(cur, pre, sizeof(pre));
flow += DFS(s, INF);
}
return flow;
} void solve()
{
scanf("%d", &n);
memset(pre, -1, sizeof(pre));
memset(deg, 0, sizeof(deg));
memset(vis, 0, sizeof(vis));
for(int i=0; i<27; i++) fa[i] = i;
ecnt = 0;
int rev; char str[27];
for(int i=0; i<n; i++)
{
scanf("%s%d", str, &rev);
int u = str[0]-'a', v = str[strlen(str)-1]-'a';
deg[u]--; deg[v]++;
vis[u] = vis[v] = true;
s = u;
if(rev) addedge(u, v, 1);
Union(u,v);
}
t = -1;
printf("Case %d: ", cas++);
if(!is_ok()) {
puts("Poor boy!");
return ;
}
if(t!=-1) addedge(t, s, 1);
s = 26, t = 27;
int fulflow = 0, flow;
for(int i=0; i<26; i++)
{
if(deg[i]==0) continue;
if(deg[i]<0) addedge(s, i, -deg[i]/2);
else addedge(i, t, deg[i]/2), fulflow+=deg[i]/2;
}
flow = Maxflow();
puts(flow==fulflow?"Well done!":"Poor boy!");
} int main()
{
// freopen("in.txt", "r", stdin);
cin>>_;
while(_--) solve();
return 0;
}
上一篇:Java中正则表达式去除html标签


下一篇:小白初入Linux之Nginx配置