青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 7,comments - 3,trackbacks - 0

1099. Work Scheduling

Time Limit: 0.5 second
Memory Limit: 16 MB
There is certain amount of night guards that are available to protect the local junkyard from possible junk robberies. These guards need to scheduled in pairs, so that each pair guards at different night. The junkyard CEO ordered you to write a program which given the guards characteristics determines the maximum amount of scheduled guards (the rest will be fired). Please note that each guard can be scheduled with only one of his colleagues and no guard can work alone.

Input

The first line of the input contains one number N ≤ 222 which is the amount of night guards. Unlimited number of lines consisting of unordered pairs (ij) follow, each such pair means that guard #i and guard #j can work together, because it is possible to find uniforms that suit both of them (The junkyard uses different parts of uniforms for different guards i.e. helmets, pants, jackets. It is impossible to put small helmet on a guard with a big head or big shoes on guard with small feet). The input ends with Eof.

Output

You should output one possible optimal assignment. On the first line of the output write the even number C, the amount of scheduled guards. Then output C/2 lines, each containing 2 integers (ij) that denote that i and j will work together.

Sample

inputoutput
3
1 2
2 3
1 3
2
1 2
Problem Author: Jivko Ganev



模板題.....一般圖匹配主要看模板,剩下的就是自己YY建圖了.....

模板:
#include <cstdio>
#include 
<cstring>
#include 
<algorithm>
#include 
<iostream>
#define MAXN 256
using namespace std;

struct Graph
{
    
bool mat[MAXN + 1][MAXN + 1];
    
int n;

    
bool inque[MAXN + 1];
    
int que[MAXN], head, tail;

    
int match[MAXN + 1], father[MAXN + 1], base[MAXN + 1];

    
void init(int _n)
    {
        n 
= _n;
        
for (int i = 1; i <= n; ++i)
        {
            match[i] 
= 0;
            
for (int j = 1; j <= n; ++j)
                mat[i][j] 
= false;
        }
    }

    
int pop()
    {
        
return que[head++];
    }

    
void push(int x)
    {
        que[tail
++= x;
        inque[x] 
= true;
    }

    
void add_edge(int a, int b)
    {
        mat[a][b] 
= mat[b][a] = true;
    }

    
int inpath[MAXN + 1];
    
static int pcnt;

    
int find_ancestor(int u, int v)
    {
        
++pcnt;
        
while (u)
        {
            u 
= base[u];
            inpath[u] 
= pcnt;
            u 
= father[match[u]];
        }

        
while (true)
        {
            v 
= base[v];
            
if (inpath[v] == pcnt)
                
return v;
            v 
= father[match[v]];
        }
    }

    
int inblossom[MAXN + 1];
    
static int bcnt;

    
void reset(int u, int anc)
    {
        
while (u != anc)
        {
            
int v = match[u];
            inblossom[
base[v]] = bcnt;
            inblossom[
base[u]] = bcnt;
            v 
= father[v];
            
if (base[v] != anc) father[v] = match[u];
            u 
= v;
        }
    }

    
void contract(int u, int v)
    {
        
int anc = find_ancestor(u, v);
        
++bcnt;
        reset(u, anc);
        reset(v, anc);
        
if (base[u] != anc) father[u] = v;
        
if (base[v] != anc) father[v] = u;
        
for (int i = 1; i <= n; ++i)
            
if (inblossom[base[i]] == bcnt)
            {
                
base[i] = anc;
                
if (!inque[i]) push(i);
            }
    }

    
int find_augment(int start)
    {
        
for (int i = 1; i <= n; ++i)
        {
            father[i] 
= 0;
            inque[i] 
= false;
            
base[i] = i;
        }
        head 
= 0, tail = 0, push(start);
        
while (head < tail)
        {
            
int u = pop();
            
for (int v = 1; v <= n; ++v)
                
if (mat[u][v] && base[v] != base[u] && match[v] != u)
                {
                    
if (v == start || (match[v] && father[match[v]]))
                        contract(u, v);
                    
else
                    {
                        
if (father[v] == 0)
                        {
                            
if (match[v])
                            {
                                push(match[v]);
                                father[v] 
= u;
                            }
                            
else
                            {
                                father[v] 
= u;
                                
return v;
                            }
                        }
                    }
                }
        }
        
return 0;
    }

    
void augment(int finish)
    {
        
int u = finish, v, w;
        
while (u)
        {
            v 
= father[u];
            w 
= match[v];
            match[u] 
= v;
            match[v] 
= u;
            u 
= w;
        }
    }

    
int graph_max_match()
    {
        
int ans = 0;
        
for (int i = 1; i <= n; ++i)
            
if (match[i] == 0)
            {
                
int finish = find_augment(i);
                
if (finish)
                {
                    augment(finish);
                    ans 
+= 2;
                }
            }
        
return ans;
    }
} g;

int Graph :: bcnt = 0, Graph :: pcnt = 0;

int main()
{
    
int n;
    scanf(
"%d"&n);
    g.init(n);
    
int a, b;
    
while (scanf("%d%d"&a, &b) != EOF)
        g.add_edge(a, b);
    printf(
"%d\n", g.graph_max_match());
    
for (int i = 1; i <= n; ++i)
        
if (g.match[i])
        {
            printf(
"%d %d\n", i, g.match[i]);
            g.match[g.match[i]] 
= 0;
        }
    
return 0;
}

posted on 2011-10-15 22:16 LLawliet 閱讀(305) 評論(0)  編輯 收藏 引用 所屬分類: 圖論
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲韩国一区二区三区| 欧美日韩一区二| 国产在线高清精品| 欧美一区二区三区免费视| 亚洲午夜精品久久久久久浪潮 | 99精品欧美一区二区三区| 欧美日韩在线观看视频| 午夜国产欧美理论在线播放 | 欧美高清视频一区二区三区在线观看 | 欧美成人午夜剧场免费观看| 久久亚洲综合网| 一区二区国产在线观看| 亚洲性感美女99在线| 狠狠色狠狠色综合系列| 亚洲第一黄色网| 欧美激情影音先锋| 亚洲制服丝袜在线| 亚洲一二三级电影| 国产在线观看一区| 欧美好骚综合网| 欧美精品日本| 在线成人中文字幕| 亚洲盗摄视频| 欧美另类69精品久久久久9999| 亚洲人成在线播放网站岛国| 亚洲欧洲综合另类| 欧美午夜不卡| 免费看亚洲片| 美女精品视频一区| 亚洲欧美在线播放| 久久久伊人欧美| 一本久久综合| 香蕉亚洲视频| 亚洲精品国产精品乱码不99按摩 | 性色av一区二区三区| 久久黄色网页| 中文久久乱码一区二区| 欧美一二三区在线观看| 亚洲青色在线| 亚洲欧美日韩国产一区二区三区 | 亚洲欧美日韩久久精品| 亚洲黄一区二区| 亚洲欧美国产制服动漫| 91久久精品美女高潮| 亚洲欧美日韩中文视频| 91久久视频| 欧美伊人久久久久久午夜久久久久| 亚洲黄网站在线观看| 欧美亚洲免费电影| 一区二区国产精品| 牛牛精品成人免费视频| 欧美在线中文字幕| 欧美色中文字幕| 亚洲第一久久影院| 韩日精品视频一区| 亚洲精品一区二区在线| 在线不卡a资源高清| 亚洲欧美综合| 亚洲一品av免费观看| 女女同性女同一区二区三区91| 欧美亚洲在线观看| 欧美色播在线播放| 亚洲激情在线| 亚洲国产精品久久91精品| 亚洲视频在线看| 亚洲国产精品一区二区久 | 久久狠狠久久综合桃花| 欧美亚男人的天堂| 亚洲伊人网站| 久久久久在线观看| 亚洲福利电影| 欧美国产视频日韩| 亚洲精选一区二区| 亚洲在线播放| 国产视频精品免费播放| 久久精品国产亚洲aⅴ| 牛牛国产精品| 亚洲伦理网站| 国产精品久久久久久久午夜片| 亚洲性感激情| 老司机午夜免费精品视频| 亚洲黄色影院| 欧美体内she精视频在线观看| 亚洲香蕉视频| 老司机一区二区三区| av不卡在线观看| 国产精品v日韩精品v欧美精品网站| 亚洲尤物影院| 欧美成人国产一区二区| 亚洲视频观看| 国内精品一区二区三区| 欧美高清视频免费观看| 亚洲性夜色噜噜噜7777| 久久精品视频在线播放| 国产日本欧美在线观看| 亚洲欧美国产77777| 久久久久国内| 亚洲区一区二| 欧美色123| 欧美一区日本一区韩国一区| 美女在线一区二区| 艳妇臀荡乳欲伦亚洲一区| 欧美日韩中文字幕在线视频| 亚洲欧美日韩精品久久久久| 看欧美日韩国产| 亚洲美女一区| 欧美日韩亚洲综合| 久久综合久久久| 99国产精品视频免费观看| 久久精品日产第一区二区| 亚洲国产高清高潮精品美女| 欧美日韩久久久久久| 亚洲欧美久久久久一区二区三区| 久久久久久久综合| 99re66热这里只有精品3直播| 国产精品www.| 猫咪成人在线观看| 亚洲一区二区久久| 欧美高清视频| 亚洲欧美日韩精品久久久久| 99亚洲视频| 国产亚洲欧美日韩在线一区| 欧美大片免费| 欧美一区二区三区在线看| 亚洲免费av电影| 美女网站久久| 欧美专区日韩视频| 亚洲一卡久久| 亚洲精品视频一区| 红桃av永久久久| 欧美日韩亚洲一区| 欧美精品一二三| 久久美女性网| 亚洲欧美激情精品一区二区| 亚洲激情电影在线| 久久综合中文字幕| 欧美中文字幕不卡| 亚洲在线观看| 夜夜精品视频一区二区| 亚洲国产欧美日韩精品| 国产亚洲欧美一区| 欧美日韩色一区| 久久久久久亚洲精品中文字幕| 亚洲在线黄色| 欧美国产精品人人做人人爱| 欧美成人免费va影院高清| 久久久久久久一区二区三区| 欧美在线观看你懂的| 亚洲欧美日韩一区在线| 在线视频日韩| 一区二区三区精品视频| 亚洲美女毛片| 99亚洲一区二区| 在线视频日韩| 亚洲一区二区三区四区视频| 亚洲免费观看高清完整版在线观看熊| 尤物视频一区二区| 亚洲国产精品传媒在线观看| 在线免费高清一区二区三区| 一色屋精品视频免费看| 在线精品在线| 亚洲精品视频在线| 一本久久青青| 亚洲久久一区二区| 亚洲欧美精品在线| 欧美一级播放| 久久美女艺术照精彩视频福利播放| 久久精品一区二区三区中文字幕| 欧美中文在线免费| 免费亚洲视频| 久久一综合视频| 老司机午夜精品| 亚洲激情国产| 一区二区三区 在线观看视| 亚洲手机成人高清视频| 欧美亚洲免费高清在线观看| 久久久久成人精品| 欧美激情一二三区| 国产精品久久久久久久久久久久 | 欧美本精品男人aⅴ天堂| 亚洲国产精品v| 这里只有精品视频| 在线亚洲免费视频| 亚洲欧美精品一区| 久久久久久久精| 欧美日本二区| 国产一区深夜福利| 亚洲老板91色精品久久| 香蕉精品999视频一区二区| 另类激情亚洲| 免费久久99精品国产| 99re66热这里只有精品4| 亚洲一区二三| 欧美a级一区| 国产欧美日韩免费看aⅴ视频| 91久久精品国产| 午夜欧美精品久久久久久久| 欧美黑人在线观看| 亚洲主播在线播放| 噜噜噜91成人网|