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

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>
            欧美日韩国产电影| 欧美成人午夜视频| 国产精品丝袜久久久久久app| 日韩亚洲精品电影| 99热精品在线| 国产丝袜一区二区| 免费成人毛片| 欧美乱人伦中文字幕在线| 亚洲视频一区二区在线观看 | 久久久噜噜噜| 久久久久久久久伊人| 最新高清无码专区| 一区二区三区成人| 国内揄拍国内精品少妇国语| 欧美韩日高清| 国产精品视频一二三| 免费在线日韩av| 欧美性做爰猛烈叫床潮| 久久综合国产精品| 欧美午夜大胆人体| 女人天堂亚洲aⅴ在线观看| 欧美日韩国产电影| 久久在精品线影院精品国产| 欧美精品性视频| 久久久青草婷婷精品综合日韩 | 欧美国产日韩一区二区| 亚洲欧美一区二区视频| 久久久久久久久久久久久久一区| 99国内精品久久| 久久精品国产77777蜜臀| 亚洲视频一区二区| 免费在线观看日韩欧美| 欧美一区激情视频在线观看| 欧美精品午夜| 欧美不卡一区| 国产日韩欧美一区二区三区四区| 亚洲精品午夜| 亚洲国产欧美一区| 欧美在线观看视频一区二区三区| 一二三区精品福利视频| 麻豆国产精品一区二区三区| 欧美一级淫片播放口| 欧美日韩精品在线| 欧美激情导航| 一区视频在线| 欧美自拍丝袜亚洲| 久久国产精品久久久久久电车| 欧美日韩国产91| 亚洲国产美女| 在线看片日韩| 久热精品视频在线免费观看 | 99热在这里有精品免费| 久久亚洲春色中文字幕久久久| 欧美亚洲视频在线观看| 欧美视频第二页| 亚洲免费av观看| 99re6这里只有精品| 欧美电影免费观看网站| 欧美激情亚洲一区| 亚洲激情网址| 欧美福利一区二区| 亚洲日本中文字幕免费在线不卡| 亚洲国产日韩一区二区| 麻豆精品视频| 亚洲高清二区| 一本一本久久a久久精品综合麻豆 一本一本久久a久久精品牛牛影视 | 亚洲欧洲一区二区三区在线观看| 久久国产精品黑丝| 久久尤物视频| 亚洲日本中文字幕| 欧美精品一线| 在线综合亚洲欧美在线视频| 亚洲男女毛片无遮挡| 国产精品女主播在线观看| 亚洲欧美日本在线| 久久亚洲春色中文字幕| 亚洲国产高潮在线观看| 欧美风情在线| 一区二区三区精品视频在线观看 | 在线观看视频一区| 欧美aaaaaaaa牛牛影院| 亚洲九九精品| 欧美一区二区久久久| 一区二区在线看| 欧美精彩视频一区二区三区| 一本色道精品久久一区二区三区| 欧美一级在线视频| 亚洲国产成人一区| 欧美日韩精品一区视频| 午夜激情综合网| 亚洲高清视频在线| 午夜精品久久久久影视| 精品成人久久| 欧美日韩视频在线一区二区| 欧美一区二区播放| 亚洲激情社区| 久久久欧美精品| 亚洲午夜电影| 亚洲成人自拍视频| 国产精品免费看| 美日韩在线观看| 亚洲欧美日韩在线观看a三区 | 久久精品一二三区| 日韩网站在线观看| 国产一区二区久久久| 欧美日韩高清免费| 久久深夜福利| 亚洲欧美日韩国产成人| 亚洲黄色性网站| 久久综合五月| 欧美在线视频免费播放| 夜夜精品视频| 亚洲国产一区二区三区青草影视| 国产精品久久久久影院亚瑟| 米奇777超碰欧美日韩亚洲| 亚洲一区二区少妇| 91久久在线| 欧美69视频| 久久九九国产精品| 亚洲一区二区三区高清| 亚洲日本电影| 在线欧美三区| 国内精品久久久久久久果冻传媒| 国产精品第一区| 欧美日本在线看| 欧美韩日一区二区| 久久综合九色九九| 久久精品视频播放| 欧美在线一级视频| 亚洲欧美成人一区二区在线电影| 亚洲日本成人| 亚洲全部视频| 亚洲国产天堂久久国产91| 欧美不卡在线视频| 欧美激情一二区| 欧美成人日本| 欧美黄色免费| 亚洲电影免费观看高清完整版在线| 久久人91精品久久久久久不卡| 久久爱www久久做| 欧美一区三区三区高中清蜜桃 | 亚洲国产一区二区三区青草影视| 一区二区在线视频播放| 一区二区亚洲精品| 在线观看91精品国产麻豆| 影音先锋成人资源站| 亚洲成色www8888| 亚洲黄色影片| 夜夜爽www精品| 亚洲性人人天天夜夜摸| 午夜一级久久| 久久精品99国产精品| 玖玖玖免费嫩草在线影院一区| 久久深夜福利免费观看| 蜜臀va亚洲va欧美va天堂| 欧美高清视频一区二区三区在线观看 | 精品96久久久久久中文字幕无| 国产一区二区三区四区hd| 在线日韩av| 亚洲美女中出| 性久久久久久久久| 久久这里有精品15一区二区三区| 欧美电影在线| 99伊人成综合| 欧美在线短视频| 欧美大片91| 国产精品揄拍一区二区| 又紧又大又爽精品一区二区| 99国产精品久久久久久久久久| 欧美一区二区国产| 欧美激情亚洲自拍| 亚洲欧美国产精品va在线观看 | 欧美大色视频| 国产精品日韩精品| 亚洲国产美女久久久久| 亚洲永久字幕| 欧美.www| 亚洲欧美日韩中文在线制服| 免费在线看成人av| 国产精品网站一区| 亚洲欧洲一区二区在线观看 | 亚洲国产毛片完整版| 亚洲一区二区三区国产| 欧美电影免费观看高清| 亚洲一区二区三区成人在线视频精品 | 久久久不卡网国产精品一区| 亚洲大片av| 欧美一区中文字幕| 欧美日韩一区二区三区| 亚洲国产欧美一区二区三区丁香婷| 亚洲欧美视频一区二区三区| 亚洲国产欧美一区二区三区同亚洲 | 久久久久免费观看| 中文国产成人精品| 欧美另类变人与禽xxxxx| 激情五月婷婷综合| 亚欧美中日韩视频| 一区二区国产在线观看| 欧美韩日精品| 亚洲高清免费视频|