POJ 1637 Sightseeing tour - nazgul's Blog

POJ 1637 Sightseeing tour

nazgul posted @ 2011年3月02日 09:49 in POJ , 2208 阅读

以下解释来源于其他牛人：

把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。
好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以2，得x。也就是说，对于每一个点，只要将x条边改变方向（入>出就是变入，出>入就是
9
变出），就能保证出=入。如果每个点都是出=入，那么很明显，该图就存在欧拉回路。
现在的问题就变成了：我该改变哪些边，可以让每个点出=入？构造网络流模型。首先，有向边是不能改变方向的，要之无用，删。一开始不是把无向边定向了吗？定的是什么向，就把网络构建成什么样，边长容量上限1。另新建s和t。对于入>出的点u，连接边(u, t)、容量为x，对于出>入的点v，连接边(s, v)，容量为x（注意对不同的点x不同）。之后，察看是否有满流的分配。有就是能有欧拉回路，没有就是没有。欧拉回路是哪个？察看流值分配，将所有流量非 0（上限是1，流值不是0就是1）的边反向，就能得到每点入度=出度的欧拉图。
由于是满流，所以每个入>出的点，都有x条边进来，将这些进来的边反向，OK，入=出了。对于出>入的点亦然。那么，没和s、t连接的点怎么办？和s连接的条件是出>入，和t连接的条件是入>出，那么这个既没和s也没和t连接的点，自然早在开始就已经满足入=出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
所以，就这样，混合图欧拉回路问题，解了。

如果这道题用矩阵，需要注意两点直接可能有有条边，容量要相加。

 

 

?
矩阵方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdio.h>
#include <string.h>
#define MAXN    210
#define MIN( a, b ) (a) > (b) ? (b) : (a)
 
int ent[MAXN];
int map[MAXN][MAXN], flow[MAXN][MAXN];
 
int EK( int num, int s, int t )
{
    int my_queue[MAXN], head, tail;
    int pre[MAXN], min_flow[MAXN];
    int ans = 0, i, k;
    memset( flow, 0, sizeof( flow ) );
    while ( 1 )
    {
        head = 0; tail = 1;
        my_queue[0] = s;
        memset( pre, -1, sizeof( pre ) );
        min_flow[s] = 0x7fffffff;
        pre[s] = -2;
        while ( head < tail )
        {
            k = my_queue[head++];
            for ( i = 0; i < num; ++i )
            {
                if ( pre[i]==-1 && flow[k][i]<map[k][i] )
                {
                    my_queue[tail++] = i;
                    pre[i] = k;
                    min_flow[i] = MIN( min_flow[k], ( map[k][i]-flow[k][i] ) );
                }
            }
            if ( pre[t] != -1 )
            {
                k = t;
                while ( pre[k] >= 0 )
                {
                    flow[pre[k]][k] += min_flow[t];
                    flow[k][pre[k]] = -flow[pre[k]][k];
                    k = pre[k];
                }
                break;
            }
        }
        if ( pre[t] == -1 ) return ans;
        else ans += min_flow[t];
    }
}
 
int main()
{
    int n, m, x, y, z, flag, cases;
 
    //freopen( "main.in", "r", stdin );
 
    scanf( "%d", &cases );
    while ( cases-- )
    {
        flag = 1;
        memset( ent, 0, sizeof( ent ) );
        memset( map, 0, sizeof( map ) );
        scanf( "%d%d", &n, &m );
        while ( m-- )
        {
            scanf( "%d%d%d", &x, &y, &z );
            ent[x]--; ent[y]++;
            if ( z == 0 ) map[x][y]++;
        }
        for ( z = 0, y = 1; y <= n && flag; ++y )
        {
            if ( ent[y] % 2 ) flag = 0;
            x = ent[y] / 2;
            if ( x > 0 )
            {
                map[y][n+1] = x; z += x;
            }
            else
                map[0][y] = -x;
        }
        if ( flag ) x = EK( n+2, 0, n+1 );
        if ( flag && x == z )
            printf( "possible\n" );
        else
            printf( "impossible\n" );
    }
    return 0;
}

 

?
邻接表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
#include <string.h>
#define MAXN 210
#define MAXM 2500
 
int MIN( int a, int b )
{
    return a > b ? b : a;
}
 
typedef struct node
{
    int f, c, u, v;
    struct node *rev, *next;
}tnode, *pnode;
tnode   edge[MAXM];
pnode   g[MAXN], pre[MAXN];
int     now, ent[MAXN];
 
void addEdge( int u, int v, int c, int k )
{
    pnode p = &edge[now];
    p->c = c; p->u = u; p->v = v;
    p->next = g[u];
    if ( k != -1 ) p->rev = &edge[k];
    g[u] = p; now++;
}
 
int EK( int num, int sour, int sink )
{
    int my_queue[MAXN], head, tail;
    int min_flow[MAXN], ans = 0;
    pnode p;
 
    while ( 1 )
    {
        head = 0; tail = 1;
        my_queue[0] = sour;
        memset( pre, 0, sizeof( pre ) );
        min_flow[sour] = 0x7fffffff;
        while ( head < tail )
        {
            int t = my_queue[head++];
            for ( p = g[t]; p; p = p->next )
            if ( pre[p->v] == 0 && p->f < p->c )
            {
                my_queue[tail++] = p->v;
                pre[p->v] = p;
                min_flow[p->v] = MIN( min_flow[t], ( p->c - p->f ) );
            }
            if ( pre[sink] )
            {
                for ( p = pre[sink]; p; p = pre[p->u] )
                {
                    p->f += min_flow[sink];
                    if ( p->rev ) p->rev->f = -p->f;
                }
                break;
            }
        }
        if ( pre[sink] == 0 ) return ans;
        else ans += min_flow[sink];
    }
}
 
int main()
{
    int n, m, x, y, z, flag, cases;
    //freopen( "main.in", "r", stdin );
    scanf( "%d", &cases );
    while ( cases-- )
    {
        flag = 1; now = 0;
        memset( ent, 0, sizeof( ent ) );
        memset( edge, 0, sizeof( edge ) );
        memset( g, 0, sizeof( g ) );
        scanf( "%d%d", &n, &m );
        while ( m-- )
        {
            scanf( "%d%d%d", &x, &y, &z );
            ent[x]--; ent[y]++;
            if ( z == 0 )
            {
                addEdge( x, y, 1, now+1 );
                addEdge( y, x, 0, now-1 );
            }
        }
        for ( z = 0, y = 1; y <= n && flag; ++y )
        if ( ent[y] != 0 )
        {
            if ( ent[y] & 1 ) flag = 0;
            x = ent[y] / 2;
            if ( x > 0 )
            {
                addEdge( y, n+1, x, -1 );
                z += x;
            }
            else
                addEdge( 0, y, -x, -1 );
        }
        if ( flag ) x = EK( n+2, 0, n+1 );
        if ( flag && x == z )
            printf( "possible\n" );
        else
            printf( "impossible\n" );
    }
    return 0;
}

 

Small_feed 评论 (24)
1
[回复]
Avatar_small
seo service UK 说:
2024年10月21日 15:11

Glad to chat your blog, I seem to be forward to more reliable articles and I think we all wish to thank so many good articles, blog to share with us. First of all let me tell you, you have got a great blog .I am interested in looking for more of such topics and would like to have further information

2
[回复]
Avatar_small
contents 说:
2024年10月21日 15:22

I can see that your business

3
[回复]
Avatar_small
good contents 说:
2024年10月21日 15:24

I would like to thank you for the efforts you’ve put in writing this blog.

4
[回复]
Avatar_small
토디즈 说:
2024年10月21日 15:24

There are actually lives.

5
[回复]
Avatar_small
토토사이트 说:
2024年10月21日 15:26

they have a system that allows users to leave comments about the work workshop, which will allow to the platform mostbet improve own service.

6
[回复]
Avatar_small
read more 说:
2024年10月21日 15:28

An intriguing discussion is next! Cheers.

7
[回复]
Avatar_small
Learn more 说:
2024年10月21日 15:30

This is my first time i visit keep up the excellent work

8
[回复]
Avatar_small
get more info 说:
2024年10月21日 15:34

There are actually numerous pleasure, for the remainder of their lives.

9
[回复]
Avatar_small
click here 说:
2024年10月21日 15:36

Hi, I log on to your new stuff regularly. Your story-telling style is awesome, keep doing what you’re doing!

10
[回复]
Avatar_small
토토쿠 说:
2024年10月21日 15:38

I am unable to comments that don’t add to the discussion!

11
[回复]
Avatar_small
get more info 说:
2024年10月21日 15:39

you have any questions relating to where and the best ways to utilize why is klonopin so addictive to abuse psychology, you can contact us at our web

12
[回复]
Avatar_small
토토서치 说:
2024年10月21日 15:40

I can see that you are an expert at your field! I am launching a website soon, and your information will be very useful for me .. Thanks for all your help and wishing you all the success in your business

13
[回复]
Avatar_small
check here 说:
2024年10月21日 16:57

The next time I read a blog, I hope that it doesnt disappoint me as much as this one. I mean, I know it was my choice to read, but I actually thought you have something interesting to say. All I hear is a bunch of whining about something that you could fix if you weren’t too busy looking for attention

14
[回复]
Avatar_small
information 说:
2024年10月21日 17:11

not certain whether or not this post is written via him as no one else know such special about my trouble

15
[回复]
Avatar_small
개구리토토 说:
2024年10月21日 17:29

Hi there, for all time i used to check blog posts here in the early hours in the dawn,for the reason that i enjoy to gain knowledge of more and more.

16
[回复]
Avatar_small
information 说:
2024年10月21日 17:29

Hi, I log on to your new stuff regularly. Your story-telling style is awesome, keep doing what you’re doing!

17
[回复]
Avatar_small
토토시대 说:
2024年10月21日 17:30

Very good info. Lucky me I recently found your blog by chance (stumbleupon).

18
[回复]
Avatar_small
먹튀히어로 说:
2024年10月21日 17:38

Hi, I log on to your new stuff regularly. Your story-telling style is awesome, keep doing what you’re doing!

19
[回复]
Avatar_small
good information 说:
2024年10月21日 17:39

Hello, the discounts and campaigns on your website are very advantageous for dermocosmetics and supplements. This allows me to shop at very affordable prices.

20
[回复]
Avatar_small
onlinecasinokr365 说:
2024年10月21日 17:41

Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me.

21
[回复]
Avatar_small
accurate content 说:
2024年10月21日 17:51

I can see that you are an expert at your field! I am launching a website soon, and your information will be very useful for me.. Thanks for all your help and wishing you all the success in your business

22
[回复]
Avatar_small
website 说:
2024年10月21日 17:55

The next time I read a blog, I hope that it doesnt disappoint me as much as this one. I mean, I know it was my choice to read, but I actually thought you have something interesting to say. All I hear is a bunch of whining about something that you could fix if you weren’t too busy looking for attention

23
[回复]
Avatar_small
click here 说:
2024年10月21日 18:03

Article writing is also a fun, if you be familiar with then you can write otherwise it is complex to write.

24
[回复]
Avatar_small
Learn more 说:
2024年10月21日 18:39

I would like to thank you for the efforts you’ve put in writing this site.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee