【POJ】【1637】Sightseeing tour

网络流/最大流



  愚人节快乐XD

  这题是给一个混合图(既有有向边又有无向边),让你判断是否有欧拉回路……

  我们知道如果一个【连通】图中每个节点都满足【入度=出度】那么就一定有欧拉回路……

  那么每条边都可以贡献一个出度出来,对于一条边u->v:

    连S->edge cap=1;

    如果是有向边,就连 edge->v cap=1;

    否则(无向边)连edge->u cap=1, edge->v cap=1;

  然后每个点的总度数我们是知道的……那么它最后的【出度】就等于 总度数/2。(这个地方我傻逼了没想到……

  P.S.这题是跟POJ2699比较类似的

 1 Source Code
 2 Problem: 1637        User: sdfzyhy
 3 Memory: 1148K        Time: 32MS
 4 Language: G++        Result: Accepted
 5
 6     Source Code
 7
 8     //BZOJ 1000
 9     #include<vector>
10     #include<cstdio>
11     #include<cstdlib>
12     #include<cstring>
13     #include<iostream>
14     #include<algorithm>
15     #define rep(i,n) for(int i=0;i<n;++i)
16     #define F(i,j,n) for(int i=j;i<=n;++i)
17     #define D(i,j,n) for(int i=j;i>=n;--i)
18     using namespace std;
19
20     int getint(){
21         int v=0,sign=1; char ch=getchar();
22         while(ch<‘0‘||ch>‘9‘) {if (ch==‘-‘) sign=-1; ch=getchar();}
23         while(ch>=‘0‘&&ch<=‘9‘) {v=v*10+ch-‘0‘; ch=getchar();}
24         return v*sign;
25     }
26     typedef long long LL;
27     const int N=100010,M=100010,INF=~0u>>2;
28     /*******************tamplate********************/
29     int n,m,ans,du[1000];
30     struct edge{int to,v;};
31     struct Net{
32         edge E[M];
33         int next[M],head[N],cnt;
34         void ins(int x,int y,int z){E[++cnt]=(edge){y,z};next[cnt]=head[x];head[x]=cnt;}
35         void add(int x,int y,int z){ins(x,y,z); ins(y,x,0);}
36         int S,T,d[N],Q[M],cur[N];
37         bool mklevel(){
38             F(i,0,T) d[i]=-1;
39             int l=0,r=-1;
40             Q[++r]=S; d[S]=0;
41             while(l<=r){
42                 int x=Q[l++];
43                 for(int i=head[x];i;i=next[i])
44                     if(E[i].v && d[E[i].to]==-1){
45                         d[E[i].to]=d[x]+1;
46                         Q[++r]=E[i].to;
47                     }
48             }
49             return d[T]!=-1;
50         }
51         int dfs(int x,int a){
52             if(x==T)return a;
53             int flow=0;
54             for(int &i=cur[x];i && flow<a;i=next[i])
55                 if(E[i].v && d[E[i].to]==d[x]+1){
56                     int f=dfs(E[i].to,min(a-flow,E[i].v));
57                     E[i].v-=f;
58                     E[i^1].v+=f;
59                     flow+=f;
60                 }
61             if(!flow) d[x]=-1;
62             return flow;
63         }
64         void Dinic(){
65             while(mklevel()){
66                 F(i,S,T) cur[i]=head[i];
67                 ans+=dfs(S,INF);
68             }
69         }
70         void init(){
71             n=getint(); m=getint();
72             cnt=1; memset(head,0,sizeof head);
73             F(i,1,n) du[i]=0;
74             S=0; T=n+m+2; ans=0;
75             int x,y,z;
76             F(i,1,m){
77                 x=getint(); y=getint(); z=getint();
78                 add(S,i,1); add(i,y+m,1);
79                 if (!z) add(i,x+m,1);
80                 du[x]++; du[y]++;
81             }
82             F(i,1,n){
83                 if (du[i]%2){puts("impossible");return;}
84                 add(i+m,T,du[i]/2);
85             }
86             Dinic();
87             if (ans==m) puts("possible");
88             else puts("impossible");
89         }
90     }G1;
91     int main(){
92     #ifndef ONLINE_JUDGE
93         freopen("input.txt","r",stdin);
94     //    freopen("output.txt","w",stdout);
95     #endif
96         int T=getint();
97         while(T--) G1.init();
98         return 0;
99     }

时间: 03-31

【POJ】【1637】Sightseeing tour的相关文章

【POJ 2823 Sliding Window】 单调队列

题目大意:给n个数,一个长度为k(k<n)的闭区间从0滑动到n,求滑动中区间的最大值序列和最小值序列. 最大值和最小值是类似的,在此以最大值为例分析. 数据结构要求:能保存最多k个元素,快速取得最大值,更新时删去“过期”元素和“不再有希望”的元素,安放新元素. 单调队列的基本概念百度百科讲得比较清楚了:http://baike.baidu.com/view/3771451.htm 我的大致思路是: 1. 每个元素存储为结构体,包含它的秩和值.维护最大长度为k的单调队列,保证所有元素的秩都在区间内

【POJ 3669 Meteor Shower】简单BFS

流星雨撞击地球(平面直角坐标第一象限),问到达安全地带的最少时间. 对于每颗流星雨i,在ti时刻撞击(xi,yi)点,同时导致(xi,yi)和上下左右相邻的点在ti以后的时刻(包括t)不能再经过(被封锁).安全地带为永远不会被封锁的点. 简单bfs,开始WA在把平面空间上限当成300*300,但根据题目,这只是有流星雨撞击的范围.实际可走的空间理论上没上限,但分析可得,离原点最近的安全地带一定在(302,302)范围内,所以应可把数组至少开为303*303. 后来WA在把G[0][0]==1的情

【POJ】1739 Tony&#39;s Tour

http://poj.org/problem?id=1739 题意:n×m的棋盘,'#'是障碍,'.'是空白,求左下角走到右下角且走过所有空白格子的方案数.(n,m<=8) #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; #define BIT(a,b) ((a)<<((b)<<1)) #

【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.

【POJ 1408】 Fishnet (叉积求面积)

[POJ 1408] Fishnet (叉积求面积) 一个1*1㎡的池塘 有2*n条线代表渔网 问这些网中围出来的最大面积 一个有效面积是相邻两行和相邻两列中间夹的四边形 Input为n 后面跟着四行 每行n个浮点数 每一行分别代表a,b,c,d 如图 并且保证a(i) > a(i-1) b(i) > b(i-1) c(i) > c(i-1) d(i) > d(i-1) n(n <= 30)*2+4(四个岸)条边 枚举点数就行 相邻的四个四个点枚举 找出围出的最大面积 找点用

【POJ 2513】Colored Sticks

[POJ 2513]Colored Sticks 并查集+字典树+欧拉通路 第一次做这么混的题..太混了-- 不过题不算难 字典树用来查字符串对应图中的点 每个单词做一个点(包括重复单词 题意就是每个边走且直走一次(欧拉通路 欧拉图的判定: 没有或者只有两个奇数度的点的图叫做欧拉图 有这些就可以解答此题了 另外需要注意题目范围是25W个木棍 所以最多可能有50W个点 卡了好多个RE 代码如下: #include <iostream> #include <cstdlib> #incl

2292: 【POJ Challenge 】永远挑战

2292: [POJ Challenge ]永远挑战 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 553  Solved: 230[Submit][Status][Discuss] Description lqp18_31和1tthinking经常出题来虐ftiasch.有一天, lqp18_31搞了一个有向图,每条边的长度都是1. 他想让ftiasch求出点1到点 N 的最短路."水题啊.", ftiasch这么说道. 所以1tth

poj 1808 Quadratic Residues 【平方剩余】【数论】

题目链接:http://poj.org/problem?id=1808 题目大意:给你T组数据,每组数据一个a一个n,判断 x^2  ≡  a ( mod  n ) 能否成立.成立则输出1否则输出-1. 一个简单的平方剩余,只用判断能否有解即可. #include<stdio.h> #define LL long long LL pow_mod(LL a, LL n, LL mod) { LL res = 1; while(n) { if (n & 1) res = res * a %

【POJ】2278 DNA Sequence

各种wa后,各种TLE.注意若AC非法,则ACT等一定非法.而且尽量少MOD. 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 using namespace std; 6 7 #define MAXN 105 8 #define NXTN 4 9 10 char str[15]; 11 12 typedef struct Matrix {

【POJ 1201】 Intervals(差分约束系统)

[POJ 1201] Intervals(差分约束系统) 11 1716的升级版 把原本固定的边权改为不固定. Intervals Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 23817   Accepted: 9023 Description You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn. Write a p