poj1637 Sightseeing tour

poj1637 Sightseeing tour

​​ Description The city executive board in Lund wants to construct a sightseeing tour by bus in Lund, so that tourists can see every corner of the beautiful city. They want to construct the tour so that every street in the city is visited exactly once. The bus should also start and end at the same junction. As in any city, the streets are either one-way or two-way, traffic rules that must be obeyed by the tour bus. Help the executive board and determine if it’s possible to construct a sightseeing tour under these constraints.

Input On the first line of the input is a single positive integer n, telling the number of test scenarios to follow. Each scenario begins with a line containing two positive integers m and s, 1 <= m <= 200,1 <= s <= 1000 being the number of junctions and streets, respectively. The following s lines contain the streets. Each street is described with three integers, xi, yi, and di, 1 <= xi,yi <= m, 0 <= di <= 1, where xi and yi are the junctions connected by a street. If di=1, then the street is a one-way street (going from xi to yi), otherwise it’s a two-way street. You may assume that there exists a junction from where all other junctions can be reached.

Output For each scenario, output one line containing the text “possible” or “impossible”, whether or not it’s possible to construct a sightseeing tour.

Sample Input

4 5 8 2 1 0 1 3 0 4 1 1 1 5 0 5 4 1 3 4 0 4 2 1 2 2 0 4 4 1 2 1 2 3 0 3 4 0 1 4 1 3 3 1 2 0 2 3 0 3 2 0 3 4 1 2 0 2 3 1 1 2 0 3 2 0

Sample Output

possible impossible impossible possible

Source Northwestern Europe 2003 给出n个节点m条边 这些边可以是有向可以是无向 现在求这个图中是否存在欧拉回路 首先欧拉回路的定义：（摘抄自kuangbin的blog)一开始当然是判断原图的基图是否连通，若不连通则一定不存在欧拉回路或欧拉路径（不考虑度数为0的点）。

其实，难点在于图中的无向边，需要对所有的无向边定向（指定一个方向，使之变为有向边），使整个图变成一个有向欧拉图（或有向半欧拉图）。若存在一个定向满足此条件，则原图是欧拉图（或半欧拉图）否则不是。关键就是如何定向？ 相当于我需要经过图中每条边恰好一次 并且还能够绕回原点 那么经过我们观察可以发现这个满足欧拉回路的话 原图中的所有的度都将是偶数 如果一个图中度存在奇数 那么一定不存在奇数 那么如何定向? 首先可以知道 有向边的带来的度都是确定的，所以我直接累加到相应节点的度里即可 如果我们希望构成一个欧拉回路我需要先针对无向边 任意给他定向 然后并且表示出他们的度来 这时候显然有很多点的度 根本不相同 怎么办我可以调整啊 假如现在我拥有一条s->xx->xxx->t的路径 那么我如果将整条路径完全反向那么是不是只有我s,t的度会改变 并且可以观察到的是s,t改变量一定是偶数 因为进-1出+1 或者反之亦然 中间的改完都是不变的 那么是不是和网络流很像 于是构造网络求解此题 如果一个点入度<出度则源向他连d[i]/2 （表示这个点的入度太少了 我如果有流量经过他的入度就会+1）反之 他向汇连d[i]/2 然后原图中我已经定向过的边权值都为1 表示这条边我只可以反向一回 然后跑一下最大流 看是否满流 就是是否所有点入度都等于出度 然后输出即可

#include#include#include#include#define N 220#define inf 0x3f3f3f3fusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}struct node{ int y,z,next;}data[10000];int num=1,h[N],level[N],cur[N],d[N],T,TT,n,m;inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].z=0;data[num].next=h[y];h[y]=num;}inline bool bfs(){ memset(level,0,sizeof(level));level[0]=1;queueq;q.push(0); while(!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[y]||!z) continue;level[y]=level[x]+1;if (y==T) return 1;q.push(y); } }return 0;}inline int dfs(int x,int s){ if (x==T) return s;int ss=s; for (int &i=cur[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[x]+1==level[y]&&z){ int xx=dfs(y,min(z,s));if(!xx) level[y]=0; s-=xx;data[i].z-=xx;data[i^1].z+=xx;if(!s) return ss; } }return ss-s;}int main(){ freopen("poj1637.in","r",stdin); TT=read(); while(TT--){ n=read();m=read();num=1;memset(h,0,sizeof(h));memset(d,0,sizeof(d)); for (int i=1;i<=m;++i){ int x=read(),y=read(),dd=read(); if (dd) ++d[y],--d[x];else ++d[y],--d[x],insert1(x,y,1); }bool flag=0;T=n+1;int sum=0; for (int i=1;i<=n;++i){ if (d[i]&1) {flag=1;break;} if (d[i]<0) insert1(0,i,-(d[i]>>1)),sum-=d[i]>>1;else insert1(i,T,d[i]>>1); }if (flag) {puts("impossible");continue;} int ans=0;while(bfs()) memcpy(cur,h,sizeof(h)),ans+=dfs(0,inf); if (ans!=sum) puts("impossible");else puts("possible"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。