首页 > 代码库 > POJ 1637 Sightseeing tour(混合图的欧拉回路)
POJ 1637 Sightseeing tour(混合图的欧拉回路)
题目链接
建个图,套个模板。
#include <cstdio> #include <cstring> #include <iostream> #include <map> #include <algorithm> #include <vector> #include <string> #include <queue> using namespace std; #define INF 0x3ffffff struct node { int u,v,next,re,w; }edge[20001]; int first[2001],dis[2001]; int in[2001],out[2001]; int t,str,end; void CL() { t = 1; memset(first,-1,sizeof(first)); } void add(int u,int v,int w) { edge[t].u = u; edge[t].v = v; edge[t].w = w; edge[t].re = t + 1; edge[t].next = first[u]; first[u] = t ++; edge[t].u = v; edge[t].v = u; edge[t].w = 0; edge[t].re = t - 1; edge[t].next = first[v]; first[v] = t ++; } int bfs() { int u,v,i; memset(dis,-1,sizeof(dis)); queue<int> que; que.push(str); dis[str] = 0; while(!que.empty()) { u = que.front(); que.pop(); for(i = first[u];i != -1;i = edge[i].next) { v = edge[i].v; if(edge[i].w > 0&&dis[v] < 0) { dis[v] = dis[u] + 1; que.push(v); } } } if(dis[end] > 0) return 1; else return 0; } int dfs(int u,int step) { int i,temp,v,tf = 0; if(u == end) return step; for(i = first[u];i != -1;i = edge[i].next) { v = edge[i].v; if(edge[i].w > 0&&dis[v] == dis[u] + 1&&(temp = dfs(v,min(step,edge[i].w)))) { edge[i].w -= temp; edge[edge[i].re].w += temp; return temp; } } if(!tf) dis[u] = -1; return tf; } int main() { int t,i,u,v,k,n,m; scanf("%d",&t); while(t--) { memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); scanf("%d%d",&n,&m); CL(); str = 0; end = n + 1; for(i = 0;i < m;i ++) { scanf("%d%d%d",&u,&v,&k); in[u] ++; out[v] ++; if(k != 1) add(u,v,1); } for(i = 1;i <= n;i ++) { if(abs(in[i]-out[i])%2 == 1) break; } if(i != n+1) { printf("impossible\n"); continue; } int sum = 0; for(i = 1;i <= n;i ++) { if(in[i] > out[i]) { add(str,i,(in[i]-out[i])/2); sum += (in[i]-out[i])/2; } else { add(i,end,(out[i]-in[i])/2); } } int ans = 0,res; while(bfs()) { while(res = dfs(str,INF)) ans += res; } if(ans == sum) printf("possible\n"); else printf("impossible\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。