poj 图算法

”一蹦三跳“的总算是把图算法写完了，关于割边和割点的没有看，一些题目死活不过的，也没有继续改，各种模糊，各种纠结呀。（中间加杂着考试，课设，还有放假，总之写的很乱，题意的解释，思路的解释，有的直接没解释了，都很乱，代码也没有解释，有的代码也没有贴）

1. 是差分约束系统，笼统的说就是求解关于一组变量的特殊不等式组的方法。如果你给系统是由n个变量m个约束条件组成，且每个约束条件都形如不等式，那么我们可以从这m个约束条件里发现类似最短路中的三角不等式d[v] <=d[u]+w[u,v]，所以差分约束系统就可以转换为单源最短路去求解，主要是看懂题意，建图，然后就是最短路了（注意最短路权值有可能为负）

题目链接 http://poj.org/problem?id=2983

题意：给你一些关系，问你是否叙述合理。把等号转换为不等号，注意负环判断

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <math.h>
 6 #include <queue>
 7 #define N 200010
 8 #define inf 9999999
 9 
10 using namespace std;
11 
12 struct node
13 {
14     int x;
15     int y;
16     int wei;
17 }e[N];
18 int n,cnt;
19 int dis[1010];
20 bool blem()
21 {
22     int i,j;
23     for(i = 1; i <= n; i++)
24     {
25         dis[i] = inf;
26     }
27     dis[1] = 0;
28     for(i = 0; i < n - 1; i++)
29     {
30         int flag = 0;
31         for(j = 0; j < cnt; j++)
32         {
33             if(dis[e[j].y] > dis[e[j].x] + e[j].wei)
34             {
35                 dis[e[j].y] = dis[e[j].x] + e[j].wei;
36                 flag = 1;
37             }
38         }
39         if(!flag) return true;
40     }
41     for(j = 0; j < cnt; j++)
42     {
43         if(dis[e[j].y] > dis[e[j].x] + e[j].wei)
44         {
45             dis[e[j].y] = dis[e[j].x] + e[j].wei;
46             return false;
47         }
48     }
49     return true;
50 }
51 int main()
52 {
53     int i;
54     int a,b,d;
55     int m;
56     char ch;
57     //freopen("data.txt","r",stdin);
58     while(cin>>n>>m)
59     {
60         getchar();
61         cnt = 0;
62         for(i = 0; i < m; i++)
63         {
64             scanf("%c",&ch);
65             if(ch == 'P')
66             {
67                 scanf("%d%d%d",&a,&b,&d);
68                 e[cnt].x = a;
69                 e[cnt].y = b;
70                 e[cnt].wei = -d;
71                 cnt++;
72                 e[cnt].x = b;
73                 e[cnt].y = a;
74                 e[cnt].wei = d;
75                 cnt++;
76             }
77             else
78             {
79                 scanf("%d%d",&a,&b);
80                 e[cnt].x = a;
81                 e[cnt].y = b;
82                 e[cnt].wei = -1;
83                 cnt++;
84             }
85             getchar();
86         }
87         if(blem()) cout<<"Reliable\n";
88         else cout<<"Unreliable\n";
89     }
90     return 0;
91 }

题目http://poj.org/problem?id=1364

题意：给定长度为N的序列，并给M个关系，要求从第a个序列开始，向后数b个，这些序列之和会＜或＞某个值，若满足这M个关系，输出"lamentable kingdom"，否则输出"successful conspiracy"。

把> < 改为 >= <=，然后建立不等式关系 x1 - x2 <= n，然后建边dis(x2,x1)=n。然后用最短路求解

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <queue>
 6 #include <algorithm>
 7 #define _clr(a,b) (memset(a,b,sizeof(a)))
 8 #define N 110
 9 
10 using namespace std;
11 
12 struct node
13 {
14     int s,e;
15     int next;
16     int wei;
17 }map[N * 2];
18 int dis[N * 2];
19 int point[N * 2];
20 int v[N * 2];
21 int ans[N * 2];
22 int n,m;
23 int cnt;
24 void init()
25 {
26     _clr(map,0);
27     _clr(point,0xff);
28     cnt = 1;
29 }
30 void add(int s,int e,int d)
31 {
32     map[cnt].s = s;
33     map[cnt].e = e;
34     map[cnt].wei = d;
35     map[cnt].next = point[s];
36     point[s] = cnt++;
37 }
38 int blem()
39 {
40     int i;
41     _clr(dis,0xff);
42     dis[0] = 0;
43     _clr(v,0);
44     _clr(ans,0);
45     queue<int>qu;
46     for(i = 0; i <= n; i++)
47     qu.push(i);
48     //qu.push(0);
49     v[0] = 1;
50     while(!qu.empty())
51     {
52         int temp = qu.front();
53         qu.pop();
54         v[temp] = 0;
55         for(i = point[temp]; i != -1; i = map[i].next)
56         {
57             if(dis[map[i].e] > dis[temp] + map[i].wei)
58             {
59                 dis[map[i].e] = dis[temp] + map[i].wei;
60                 if(!v[map[i].e])
61                 {
62                     v[map[i].e] = 1;
63                     qu.push(map[i].e);
64                     ans[map[i].e] ++;
65                     if(ans[map[i].e] > n) return 0;
66                 }
67             }
68         }
69     }
70     return 1;
71 }
72 int main()
73 {
74     int i;
75     int a,b,d;
76     string ch;
77     //freopen("data.txt","r",stdin);
78     while(cin>>n>>m)
79     {
80         init();
81         for(i = 0; i < m; i++)
82         {
83             cin>>a>>b>>ch>>d;
84             if(ch == "gt")
85             {
86                 add(a + b,a - 1, -d - 1);
87             }
88             else if(ch == "lt")
89             {
90                 add(a - 1,a + b,d - 1);
91             }
92         }
93         if(!blem()) printf("successful conspiracy\n");
94         else printf("lamentable kingdom\n");
95     }
96     return 0;
97 }

题目：http://poj.org/problem?id=3159

题意： n个小朋友分糖，A 同学不能容忍 B 同学的糖比他多k+1(最多能多k) ，要你求n号同学最多能多1号同学多少颗糖。

分析：也就是 ai+k<=aj => aj - ai <=k，差分约束系统满足条件的a序列转成最短路径dis[j] -dis[i] <=w(i,j)最后求dis[n]-dis[1]即可，这天n 和 m 都挺大，最好用spfa来求解最短路（代码不贴了）

2. 最小费用最大流，http://www.cppblog.com/Icyflame/archive/2009/06/30/88891.html 一个简单的讲解，但是给出了核心代码。

题目：http://poj.org/problem?id=2516

题意：给出N个商店，M个仓库，K种货物，商店的需求，仓库的存货量，以及运输过程中各种货物的运费，求商店的需求能否得到满足，若满足，花费最小的运费是多少。

View Code

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <queue>
  5 #include <algorithm>
  6 #define N 110
  7 #define inf 99999999
  8 #define _clr(a,val) (memset(a,val,sizeof(a)))
  9 
 10 using namespace std;
 11 
 12 int map[N][N], flow[N][N], cost[N][N];
 13 int pre[N], min_flow[N], dis[N];
 14 int spfa(int num,int s,int e)
 15 {
 16     queue<int>qu;
 17     int i;
 18     for(i = 0; i < num; i++)
 19     {
 20         dis[i] = inf;
 21     }
 22     _clr(pre,-1);
 23     qu.push(s);
 24     dis[s] = 0;
 25     min_flow[s] = inf;
 26     while(!qu.empty())
 27     {
 28         int tem = qu.front();
 29         qu.pop();
 30         for(i = 0; i < num; i++)
 31         {
 32             if((map[tem][i] - flow[tem][i] > 0) && (dis[tem] + cost[tem][i] < dis[i]))
 33             {
 34                 dis[i] = dis[tem] + cost[tem][i];
 35                 pre[i] = tem;
 36                 qu.push(i);
 37                 min_flow[i] = min(min_flow[tem],(map[tem][i] - flow[tem][i]));
 38             }
 39         }
 40     }
 41     if(pre[e] != -1) return 1;
 42     return 0;
 43 }
 44 
 45 int mcmf(int num,int s,int e)
 46 {
 47     int t, ans = 0;
 48     _clr(flow,0);
 49     while(spfa(num,s,e))
 50     {
 51         t = e;
 52         while(pre[t] >= 0)
 53         {
 54             flow[pre[t]][t] += min_flow[e];
 55             flow[t][pre[t]] = -flow[pre[t]][t];
 56             t = pre[t];
 57         }
 58         ans += dis[e] * min_flow[e];
 59     }
 60     return ans;
 61 }
 62 
 63 int main()
 64 {
 65     int n,m,kind,ans;
 66     bool no_ans;
 67     int order[N][N],storage[N][N];
 68     int i,j,k;
 69     //freopen("data.txt","r",stdin);
 70     while(scanf("%d%d%d",&n,&m,&kind))
 71     {
 72         if(!n && !m && !kind) break;
 73         no_ans = 0;
 74         ans = 0;
 75         for(i = 0; i < n; i++)
 76         for(j = 0; j < kind; j++)
 77         scanf("%d",&order[i][j]);
 78         for(i = 0; i < m; i++)
 79         for(j = 0; j < kind; j++)
 80         scanf("%d",&storage[i][j]);
 81         for(i = 0; i < kind; i++)
 82         {
 83             int sum1 = 0;
 84             int sum2 = 0;
 85             for(j = 0; j < n; j++)
 86             sum1 += order[j][i];
 87             for(j = 0; j < m; j++)
 88             sum2 += storage[j][i];
 89             if(sum1 > sum2)
 90             {
 91                 no_ans = 1;
 92                 ans = -1;
 93                 break;
 94             }
 95         }
 96         for(i = 0; i < kind; i++)
 97         {
 98             _clr(cost,0);
 99             for(j = 0; j < n; j++)
100             {
101                 for(k = 0; k < m; k++)
102                 {
103                     scanf("%d",&cost[n + k][j]);
104                     cost[j][n + k] = -cost[n + k][j];
105                 }
106             }
107             if(no_ans) continue;
108             else
109             {
110                 _clr(map,0);
111                 for(j = 0; j < n; j++)
112                 map[j][n + m] = order[j][i];
113                 for(j = 0; j < m; j++)
114                 map[n + m + 1][j + n] = storage[j][i];
115                 for(j = n; j < n + m; j++)
116                 {
117                     for(k = 0; k < n; k++)
118                     map[j][k] = 10;
119                 }
120                 ans += mcmf(n + m + 2, n + m + 1, m + n);
121             }
122         }
123         printf("%d\n",ans);
124     }
125     return 0;
126 }

题目：http://poj.org/problem?id=2195

题意：有n个小孩和n个房间，问每个小孩都有一个房间的最小花费

View Code

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <queue>
  5 #include <stdlib.h>
  6 #define N 210
  7 #define inf 1000000001
  8 #define _clr(a,val) (memset(a,val,sizeof(a)))
  9 
 10 using namespace std;
 11 
 12 struct node
 13 {
 14     int x,y;
 15 }man[N],house[N];
 16 char str[N][N];
 17 int map[N][N];
 18 int cost[N][N];
 19 int n,m;
 20 int nman,nhouse;
 21 int ans;
 22 void mcmf(int s,int e,int n)
 23 {
 24     int i;
 25     queue<int>qu;
 26     int d[N],flow[N][N],pre[N];
 27     _clr(flow,0);
 28     int c,f;
 29     f = c = 0;
 30     for(;;)
 31     {
 32         int inq[N];
 33         for(i = 0; i < n; i++)
 34         d[i] = inf;
 35         d[s] = 0;
 36         while(!qu.empty()) qu.pop();
 37         _clr(inq,0);
 38         inq[s] = 1;
 39         qu.push(s);
 40         while(!qu.empty())
 41         {
 42             int u = qu.front();
 43             qu.pop();
 44             inq[u] = 0;
 45             for(i = 0; i < n; i++)
 46             if(map[u][i] > flow[u][i] && d[i] > d[u] + cost[u][i])
 47             {
 48                 d[i] = d[u] + cost[u][i];
 49                 pre[i] = u;
 50                 if(!inq[i])
 51                 {
 52                     inq[i] = 1;qu.push(i);
 53                 }
 54             }
 55         }
 56         if(d[e] == inf) 
 57         {
 58             break;
 59         }
 60         int a = inf;
 61         for(i = e; i != s; i = pre[i])
 62         {
 63             if(a > map[pre[i]][i] - flow[pre[i]][i])
 64             a = map[pre[i]][i] - flow[pre[i]][i];
 65         }
 66         for(i = e; i != s; i = pre[i])
 67         {
 68             flow[pre[i]][i] += a;
 69             flow[i][pre[i]] -= a;
 70         }
 71         ans += d[e] * a;
 72         f += a;
 73     }
 74 }
 75 int main()
 76 {
 77     int i,j;
 78     //freopen("data.txt","r",stdin);
 79     while(scanf("%d%d",&n,&m),m + n)
 80     {
 81         getchar();
 82         nman = nhouse = 0;
 83         for(i = 0; i < n; i++)
 84         {
 85             for(j = 0; j < m; j++)
 86             {
 87                 cin>>str[i][j];
 88                 if(str[i][j] == 'm')
 89                 {
 90                     man[nman].x = i;
 91                     man[nman].y = j;
 92                     nman++;
 93                 }
 94                 else if(str[i][j] == 'H')
 95                 {
 96                     house[nhouse].x = i;
 97                     house[nhouse].y = j;
 98                     nhouse++;
 99                 }
100             }
101         }
102         int num = nman + nhouse;
103         _clr(map,0);
104         for(i = 0; i < num + 2; i++)
105         {
106             for(j = 0; j < num + 2; j++)
107             cost[i][j] = inf;
108         }
109         for(i = 0; i < nman; i++)
110         {
111             for(j = 0; j < nhouse; j++)
112             {
113                 map[i + 1][j + nman + 1] = 1;
114                 cost[i + 1][j + nman + 1] = abs(man[i].x - house[j].x) + abs(man[i].y - house[j].y);
115                 cost[j + nman + 1][i + 1] = -cost[i + 1][j + nman + 1];
116             }
117         }
118         for(i = 1; i <= nman; i++)
119         {
120             map[0][i] = 1;
121             cost[0][i] = 0;
122         }
123         for(i = nman + 1; i <= num; i++)
124         {
125             map[i][num + 1] = 1;
126             cost[i][num + 1] = 0;
127         }
128         ans = 0;
129         mcmf(0,num + 1,num + 2);
130         cout<<ans<<endl;
131     }
132     return 0;
133 }

3. 强连通分量，强连通分量的定义参见维基百科 http://zh.wikipedia.org/wiki/%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F 虽然说是有三种方法求解，但看网上的介绍主要是用tarjin算法来写的，感觉这个人写的很详细http://www.byvoid.com/blog/scc-tarjan/对照着他的代码，和画的图，理解算法应该是不难的。

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1269

最裸的模板套用，以前看题还以为是根据dfs搜路径，然后再倒着搜一遍。原来是强连通分量题目，题意就不说了。

判断所给的点是不是在一个强连通分量里，如果是则输出“YES”，否则’NO“

View Code

 1 #include <iostream>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <stack>
 5 #include <queue>
 6 #include <math.h>
 7 #include <stdlib.h>
 8 #include <stdio.h>
 9 #define N 10010
10 #define M 50010
11 #define _clr(a,val) (memset(a,val,sizeof(a)))
12 
13 using namespace std;
14 
15 struct node
16 {
17     int from;
18     int to;
19     int next;
20 }eage[M * 2];
21 stack<int>st;
22 int n,m;
23 int dfn[N],low[N];
24 int v[N],head[N];
25 int bh[N],val[N];
26 int out[N];
27 int num,cou,ind;
28 void add(int f,int t)
29 {
30     eage[num].from = f;
31     eage[num].to = t;
32     eage[num].next = head[f];
33     head[f] = num++;
34 }
35 void tarjin(int u)
36 {
37     int j,t,s;
38     dfn[u] = low[u] = ind++;
39     v[u] = 1;
40     st.push(u);
41     for(j = head[u]; j != -1; j = eage[j].next)
42     {
43         t = eage[j].to;
44         if(!v[t])
45         {
46             tarjin(t);
47             low[u] = min(low[u],low[t]);
48         }
49         else low[u] = min(low[u],dfn[t]);
50     }
51     //cout<<"{";
52     if(dfn[u] == low[u])
53     {
54         cou++;
55         do
56         {
57             s = st.top();
58             st.pop();
59             //cout<<s<<",";
60             bh[s] = cou;
61         }while(s != u);
62         //cout<<"}";
63     }
64 }
65 int main()
66 {
67     int i;
68     int x,y;
69     //freopen("data.txt","r",stdin);
70     while(scanf("%d%d",&n,&m) != EOF)
71     {
72         if(!n && !m) break;
73         _clr(head,-1);
74         _clr(v,0);
75         _clr(dfn,0);
76         _clr(low,0);
77         _clr(bh,0);
78         num = ind = cou = 0;
79         while(m--)
80         {
81             scanf("%d%d",&x,&y);
82             add(x,y);
83         }
84 
85         for(i = 1; i <= n; i++)
86         if(!v[i]) tarjin(i);
87         //cout<<"*****\n";
88         int tem = bh[1];
89         int flag = 0;
90         for(i = 1; i <= n; i++)
91         {
92             if(tem != bh[i]) {flag = 1; break;}
93         }
94         if(!flag) cout<<"Yes\n";
95         else cout<<"No\n";
96     }
97     return 0;
98 }

题目：http://acm.hdu.edu.cn/showproblem.php?pid=3836

简单的题意就是：给出一个连通图，问加几条边可以让这个连通图变为强量同分量。max(入度为零的个数，出度为零的个数），如果原图是一个强连通的，那么输出0

View Code

 1 #include<iostream>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<stdio.h>
 5 #include<string>
 6 #define N 20005
 7 #define M 500005
 8 using namespace std;
 9 bool istack[N];
10 int dfn[N],low[N],in[N],out[N],belong[N],stack[N],head[N];
11 typedef struct str
12 {
13     int to;
14     int next;
15 }Node;
16 Node node[M];
17 int res,num,top,ind,n,m;
18 void init()
19 {
20     memset(istack,false,sizeof(istack));
21     memset(head,-1,sizeof(head));
22     memset(dfn,0,sizeof(dfn));
23     memset(low,0,sizeof(low));
24     memset(in,0,sizeof(in));
25     memset(out,0,sizeof(out));
26     memset(stack,0,sizeof(stack));
27     memset(belong,0,sizeof(belong));
28     res=num=top=0;
29     ind=1;
30 }
31 void dfs(int i)
32 {
33     dfn[i]=low[i]=ind++;
34     istack[i]=true;
35     stack[top++]=i;
36     for(int j=head[i];j!=-1;j=node[j].next)
37     {
38         int v=node[j].to;
39         if(!dfn[v])
40         {
41             dfs(v);
42             low[i]=min(low[i],low[v]);
43         }
44         else if(istack[v])
45             low[i]=min(low[i],dfn[v]);
46     }
47     int u;
48     if(dfn[i]==low[i])
49     {
50         res++;
51         do
52         {
53              u=stack[--top];
54              istack[u]=false;
55              belong[u]=res;
56         }while(u!=i);
57      }
58 }
59 void tarjan()
60 {
61     for(int i=1;i<=n;++i)
62         if(!dfn[i]) dfs(i);
63 }
64 void solve()
65 {   if(res==1) {cout<<"0"<<endl;return;}
66     for(int i=1;i<=n;++i)
67         for(int j=head[i];j!=-1;j=node[j].next)
68            if(belong[i]!=belong[node[j].to])
69            {
70                out[belong[i]]++;
71                in[belong[node[j].to]]++;
72            }
73            int p=0,q=0;
74            for(int i=1;i<=res;++i)
75            {
76                if(!out[i]) p++;
77                if(!in[i]) q++;
78            }
79            cout<<max(p,q)<<endl;
80 }
81 int main()
82 {
83     //freopen("data.txt","r",stdin);
84     while(cin>>n>>m)
85     {
86       init();
87       for(int i=0;i!=m;++i)
88       {
89           int a,b;
90            cin>>a>>b;
91            node[num].to = b;
92            node[num].next = head[a];
93            head[a] = num++;
94       }
95       tarjan();
96       solve();
97     }return 0;
98 }

题目：http://poj.org/problem?id=1236

题意：N个高校之间有一些单向的网络链接（N<100），当发布一个软件时，学校i收到软件时，它可以将软件发送给所有它链接到的学校。现在要求发布一款软件，最少需要发给多少个学校，使得所有学校都可以收到软件（问题A）。最少需要添加多少条单向网络链接，可以使得将软件任意发给一个学校，使得所有学校都可以收到（问题B）。

问题A被称为求最小基点问题，首先，求出有向图的极大强连通分量，在同一个强连通分量里的学校任意一个收到软件，整个强连通分量里的学校都可以收到。将每个强连通分量缩成一个点，构成一个新的有向无环图。当强连通分量i收到软件，那么i可达的强连通分量都可以收到软件。

我们称入度为0的强连通分量为最高强连同分量。显然，每个最高强连通分量都必须单独发送一次软件，而其他强连通分量都可以通过最高强连通分量到达。所以，最高强连通分量的个数也就是问题A的答案

问题B，是max（入度为零的个数，出度为零的个数），注意的是，当原图只有一个强连通分量是，问题B的答案是0。

View Code

  1 #include <iostream>
  2 #include <string.h>
  3 #include <algorithm>
  4 #include <stack>
  5 #include <queue>
  6 #include <math.h>
  7 #include <stdlib.h>
  8 #include <stdio.h>
  9 #define N 101
 10 #define M 10010
 11 #define inf 100000000
 12 #define _clr(a,val) (memset(a,val,sizeof(a)))
 13 
 14 using namespace std;
 15 
 16 struct node
 17 {
 18     int from;
 19     int to;
 20     int next;
 21 }eage[M * 2];
 22 int dfn[N],low[N];
 23 int head[N],v[N];
 24 int in[N],out[N];
 25 int map[N][N];
 26 int bh[N];
 27 int ind,num,cou;
 28 stack<int>st;
 29 int n,m;
 30 void add(int f,int t)
 31 {
 32     eage[num].from = f;
 33     eage[num].to = t;
 34     eage[num].next = head[f];
 35     head[f] = num++;
 36 }
 37 void tarjin(int i)
 38 {
 39     int j,s,t;
 40     dfn[i] = low[i] = ++ind;
 41     v[i] = 1;
 42     st.push(i);
 43     for(j = head[i]; j != -1; j = eage[j].next)
 44     {
 45         t = eage[j].to;
 46         if(!dfn[t])
 47         {
 48             tarjin(t);
 49             low[i] = min(low[i],low[t]);
 50         }
 51         else if(v[t]) low[i] = min(dfn[t],low[i]);
 52     }
 53     if(dfn[i] == low[i])
 54     {
 55         cou++;
 56         do
 57         {
 58             s = st.top();
 59             st.pop();
 60             bh[s] = cou;
 61             v[s] = 0;
 62         }while(i != s);
 63     }
 64 }
 65 void ca()
 66 {
 67     int i,j;
 68     for(i = 1; i <= n; i++)
 69     if(!dfn[i]) tarjin(i);
 70     _clr(out,0);
 71     _clr(in,0);
 72     for(i = 1; i <= n; i++)
 73     {
 74         for(j = head[i]; j != -1; j = eage[j].next)
 75         {
 76             int x = bh[i];
 77             int y = bh[eage[j].to];
 78             if(x != y)
 79             {
 80                 out[x]++;
 81                 in[y]++;
 82             }
 83         }
 84     }
 85     int sum = 0;
 86     int ttsum = 0;
 87     for(i = 1;i <= cou; i++)
 88     {
 89         if(!in[i]) sum++;
 90     }
 91     if(cou == 1)
 92     {
 93         cout<<sum<<"\n0\n";
 94         return ;
 95     }
 96     else
 97     for(i = 1;i <= cou; i++)
 98     {
 99         if(!out[i]) ttsum++;
100     }
101     cout<<sum<<"\n"<<max(sum,ttsum)<<endl;
102 }
103 int main()
104 {
105     int i;
106     int x;
107     //freopen("data.txt","r",stdin);
108     while(cin>>n)
109     {
110         _clr(head,-1);
111         _clr(dfn,0);
112         _clr(v,0);
113         _clr(low,0);
114         _clr(bh,0);
115         ind = 0;
116         cou = num = 0;
117         for(i = 1; i <= n; i++)
118         {
119             while(cin>>x,x)
120             {
121                 add(i,x);
122             }
123         }
124         ca();
125     }
126     return 0;
127 }

题目：http://poj.org/problem?id=2942

题目大意：骑士在圆桌上开会人数是奇数(大于1) 互相憎恨的骑士不能做在一起，问有多少个骑士永远不能坐在圆桌上，注意可以不同时坐在一起可以分批

首先是求出图中含有的块，然后找奇圈，一个连通分量里面只要有奇圈，那么这个分量里面的所有的点都可以在某个奇圈里面，判断是否为奇圈的方法是看这个图是否为二分图，如果是二分图，则一定没有奇圈，判断二分图的方法是用染色法，dfs黑白染色，将一顶点a染成黑色，和a相邻的点染成白色。这样如果一条边上的两个点的颜色相同，说明该图不是二分图。

View Code

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <stack>
  5 #define N 1010
  6 #define M 1000010
  7 #define _clr(a,val) (memset(a,val,sizeof(a)))
  8 
  9 using namespace std;
 10 
 11 struct node
 12 {
 13     int from;
 14     int to;
 15     int next;
 16 }eage[M * 2];
 17 stack<int>st;
 18 int n,m;
 19 int num,cnt;
 20 int flag,cou;
 21 int color[N],bh[N];
 22 int v[N],vis[N];
 23 int map[N][N];
 24 int head[N];
 25 int dfn[N],low[N];
 26 int val[N];
 27 void add(int f,int t)
 28 {
 29     eage[num].from = f, eage[num].to = t;
 30     eage[num].next = head[f], head[f] = num++;
 31     eage[num].from = t, eage[num].to = f;
 32     eage[num].next = head[t], head[t] = num++;
 33 }
 34 void dfs(int ind,int col)
 35 {
 36     int i,t;
 37     color[ind] = col;
 38     for(i = head[ind]; i != -1; i = eage[i].next)
 39     {
 40         t = eage[i].to;
 41         if(bh[t] != cou) continue;
 42         if(color[t] == 1 - col) continue;
 43         if(color[t] == -1) dfs(t,1 - col);
 44         else if(color[t] == col) flag = 1;
 45         if(flag) return ;
 46     }
 47 }
 48 void tarjin(int u,int f)
 49 {
 50     int i,t,s,j,ans;
 51     dfn[u] = low[u] = cnt++;
 52     vis[u] = 1;
 53     st.push(u);
 54     for(i = head[u]; i != -1; i = eage[i].next)
 55     {
 56         t = eage[i].to;
 57         if(t == f) continue;
 58         if(!vis[t])
 59         {
 60             tarjin(t,u);
 61             low[u] = min(low[u],low[t]);
 62             if(low[t] >= dfn[u])
 63             {
 64                 cou++;
 65                 ans = 0;
 66                 do
 67                 {
 68                     s = st.top();
 69                     st.pop();
 70                     val[++ans] = s;
 71                     bh[s] = cou;
 72                 }while(s != t);
 73             bh[u] = cou;
 74             val[++ans] = u;
 75             flag = 0;
 76             _clr(color,-1);
 77             dfs(u,0);
 78             if(flag)
 79             {
 80                 for(j = 1; j <= ans; j++)
 81                 v[val[j]] = 1;
 82             }
 83             }
 84         }
 85         else low[u] = min(low[u],dfn[t]);
 86     }
 87 }
 88 int main()
 89 {
 90     int i,j;
 91     int x,y;
 92     //freopen("data.txt","r",stdin);
 93     while(scanf("%d%d",&n,&m), n + m)
 94     {
 95         _clr(map,0);
 96         while(m--)
 97         {
 98             scanf("%d%d",&x,&y);
 99             map[x][y] = map[y][x] = 1;
100         }
101         num = cnt = cou = 0;
102         _clr(head,-1);
103         for(i = 1; i <= n; i++)
104         {
105             for(j = i + 1; j <= n; j++)
106             if(map[i][j] == 0)
107             {
108                 add(i,j);
109             }
110         }
111         int sum = 0;
112         _clr(bh,-1);
113         _clr(v,0);
114         _clr(vis,0);
115         _clr(dfn,0);
116         _clr(low,0);
117         for(i = 1; i <= n; i++)
118         if(!vis[i]) tarjin(i,-1);
119         for(i = 1; i <= n; i++)
120         if(v[i]) sum++;
121         printf("%d\n",n - sum);
122     }
123     return 0;
124 }

4. KM算法如果还没有看匈牙利二分匹配的，最好先去看一小那个，km是建立在二分匹配的基础上做的，一个讲解链接 http://www.cppblog.com/MatoNo1/archive/2011/07/23/151724.aspx

题目：http://poj.org/problem?id=2400

题意： n个雇主n个员工, 每个雇主对每个员工有不同的喜好值0~n-1, 0表示最喜欢, 每个员工对每个雇主也有喜好值, 定义同前, 问怎样分配使得总喜好值对2n个人取平均的值最小, 按字典序输出所有方案.

把雇主对员工的喜爱值和员工对雇主的喜爱值建立矩阵，然后用km算法模板，km一次，再用dfs搜索路径

View Code

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <algorithm>
  5 #define N 20
  6 #define inf 10000000
  7 #define _clr(a,val) (memset(a,val,sizeof(a)))
  8 
  9 using namespace std;
 10 
 11 int map[N][N],v[N];
 12 int lx[N],ly[N];
 13 int vx[N],vy[N];
 14 int match[N],path[N];
 15 int n,cnt;
 16 int dfs(int x)
 17 {
 18     int i;
 19     vx[x] = 1;
 20     for(i = 1; i <= n; i++)
 21     {
 22         if(!vy[i] && lx[x] + ly[i] == map[x][i])
 23         {
 24             vy[i] = 1;
 25             if(match[i] == -1 || dfs(match[i]))
 26             {
 27                 match[i] = x;
 28                 return 1;
 29             }
 30         }
 31     }
 32     return 0;
 33 }
 34 int km()
 35 {
 36     int i,j,k;
 37     _clr(match,-1);
 38     for(i = 1; i <= n; i++)
 39     {
 40         lx[i] = inf;
 41         for(j = 1; j <= n; j++)
 42         if(lx[i] < map[i][j]) lx[i] = map[i][j];
 43     }
 44     _clr(ly,0);
 45     for(i = 1; i <= n; i++)
 46     {
 47         while(1)
 48         {
 49             _clr(vx,0);
 50             _clr(vy,0);
 51             if(dfs(i)) break;
 52             int minn = inf;
 53             for(j = 1; j <= n; j++)
 54             {
 55                 if(vx[j])
 56                 {
 57                     for(k = 1; k <= n; k++)
 58                     if(!vy[k] && lx[j] + ly[k] - map[j][k] < minn)
 59                     {
 60                         minn = lx[j] + ly[k] - map[j][k];
 61                     }
 62                 }
 63             }
 64             for(j = 1; j <= n; j++)
 65             {
 66                 if(vx[j]) lx[j] -= minn;
 67                 if(vy[j]) ly[j] += minn;
 68             }
 69         }
 70     }
 71     int sum = 0;
 72     for(i = 1; i <= n; i++)
 73     sum -= map[match[i]][i];
 74     return sum;
 75 }
 76 void out(int sum)
 77 {
 78     int i;
 79     if(sum  > n)
 80     {
 81         printf("Best Pairing %d\n",++cnt);
 82         for(i = 1; i <= n; i++)
 83         {
 84             //if(i == n) printf("Supervisor %d with Employee %d\n",i,path[0]);
 85             //else printf("Supervisor %d with Employee %d\n",i,path[i]);
 86             printf("Supervisor %d with Employee %d\n",i,path[i]);
 87         }
 88     }
 89     else
 90     {
 91         for(i = 1; i <= n; i++)
 92         if(lx[sum] + ly[i] == map[sum][i] && !v[i])
 93         {
 94             v[i] = 1;
 95             path[sum] = i;
 96             out(sum + 1);
 97             v[i] = 0;
 98         }
 99     }
100 }
101 int main()
102 {
103     int t,cs = 0;
104     int i,j;
105     int temp;
106     //freopen("data.txt","r",stdin);
107     scanf("%d",&t);
108     while(t--)
109     {
110         _clr(map,0);
111         scanf("%d",&n);
112         for(i = 1; i <= n; i++)
113         {
114             for(j = 0; j < n; j++)
115             {
116                 scanf("%d",&temp);
117                 map[temp][i] -= j;
118             }
119         }
120         for(i = 1; i <= n; i++)
121         {
122             for(j = 0; j < n; j++)
123             {
124                 scanf("%d",&temp);
125                 map[i][temp] -= j;
126             }
127         }
128         int ans = km();
129         printf("Data Set %d, Best average difference: %.6lf\n",++cs,(ans * 1.0) / (2 * n));
130         cnt = 0;
131         _clr(path,0);
132         _clr(v,0);
133         out(1);
134         printf("\n");
135     }
136     return 0;
137 }

题目：

题意：有N个工件要在M个机器上加工，有一个N*M的矩阵描述其加工时间。同一时间内每个机器只能加工一个工件，问加工完所有工件后，使得平均加工时间最小。注意工件是有等待时间的，当一个机器在加工一个工件时，其他的都在等待即若某台机器按顺序执行k个任务，且k个任务的执行时间分别为t1,t2…tk,则k个任务的总的执行时间是
t1*k+t2*(k-1)+t3*(k-2)+…+tk-1*2+tk

建图时分两个集合 X集有N个点（N个工件），Y集是由拆分成的 N*M个点组成。即每一个工件I都可能机器J的倒数第K（1~N）个顺序完成，则这样建图：w[i][（j-1）*N+k] = -k*tmp[i][j]。然后用KM求最大权