10.05-10.11

//本周依旧做一下图算法的题目，尽量少用algorithm里的函数，自己写熟悉熟悉。

1.The Unique MST

解析：该题为次小生成树问题。

次小生成树的求解过程:

1、找到最小生成树，值为mst

2、最小生成树种的点：找到每一个点到其它点的路径上的最大边权值 dp[i][j]表示i到j路径上的最大边权值

3、加一条不在最小生成树上的边。比如i - k，同时删除在最小生成树上i -> k路径上最大的一个边权值dp[i][k]; 这样会得到 new_mst，在这些new_mst中找一个最小的，就是次小生成树的值

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 #include <string>
  6 #include <cstring>
  7 
  8 using namespace std;
  9 
 10 #define INF 1000000007
 11 #define MAXN 105
 12 #define MAX(a, b) (a > b ? a : b)
 13 #define MIN(a, b) (a < b ? a : b)
 14 
 15 struct Edge
 16 {
 17     int v;
 18     int next;
 19 }edge[100010];
 20 
 21 int t, n, m, T;
 22 int d[MAXN], vis[MAXN], pre[MAXN], head[MAXN];
 23 int g[MAXN][MAXN], dp[MAXN][MAXN], in_mst[MAXN][MAXN];
 24 
 25 void init()
 26 {
 27     t = 0;
 28     for (int i = 0; i <= n; ++i)
 29         for (int j = 0; j <= n; ++j)
 30             g[i][j] = (i == j ? 0 : INF);
 31     memset(head, -1, sizeof(head));
 32     memset(in_mst, 0, sizeof(in_mst));
 33     memset(dp, 0, sizeof(dp));
 34 }
 35 
 36 void addEdge(int u, int v)
 37 {
 38     edge[t].v = v;
 39     edge[t].next = head[u];
 40     head[u] = t++;
 41 }
 42 
 43 int prim()
 44 {
 45     int ans = 0;
 46 
 47     for (int i = 1; i <= n; ++i)
 48         d[i] = INF, pre[i] = 0, vis[i] = 0;
 49     pre[1] = 0, d[1] = 0;
 50     for (int i = 1; i <= n; ++i)
 51     {
 52         int min_cost = INF, idx = 0;
 53         for (int j = 1; j <= n; ++j)
 54             if (!vis[j] && min_cost > d[j])
 55                 min_cost = d[idx = j];
 56         vis[idx] = 1;
 57         ans += min_cost;
 58         for (int j = 1; j <= n; ++j)
 59             if (!vis[j] && d[j] > g[idx][j])
 60                 d[j] = g[idx][j], pre[j] = idx;
 61     }
 62     for (int i = 1; i <= n; ++i)
 63         if (pre[i]) in_mst[pre[i]][i] = in_mst[i][pre[i]] = 1;
 64     for (int i = 1; i <= n; ++i)
 65         if (pre[i])
 66             addEdge(pre[i], i), addEdge(i, pre[i]);
 67 
 68     return ans;
 69 }
 70 
 71 void dfs(int u, int v, int w)
 72 {
 73     vis[v] = 1;
 74     dp[u][v] = w;
 75     for (int e = head[v]; e != -1; e = edge[e].next)
 76         if (!vis[edge[e].v])
 77             dfs(u, edge[e].v, max(w, g[v][edge[e].v]));
 78 }
 79 
 80 int main()
 81 {
 82     scanf("%d", &T);
 83     while (T--)
 84     {
 85         scanf("%d%d", &n, &m);
 86         init();
 87         int u, v, w;
 88         while (m--)
 89         {
 90             scanf("%d%d%d", &u, &v, &w);
 91             g[u][v] = g[v][u] = w;
 92         }
 93         int mst = prim();
 94         int ans = INF;
 95         for (int i = 1; i <= n; ++i)
 96         {
 97             memset(vis, 0, sizeof(vis));
 98             dfs(i, i, 0);
 99         }
100         for (int i = 1; i <= n; ++i)
101             for (int j = i+1; j <= n; ++j)
102                 if (!in_mst[i][j] && g[i][j] != INF)
103                     ans = min(ans, mst-dp[i][j]+g[i][j]);
104         if (ans == mst) puts("Not Unique!");
105         else printf("%d
", mst);
106     }
107 
108     return 0;
109 }

View Code

2.Sorting It All Out

 1 //添加一条边就要判断一下，最后判断出Sorted sequence cannot be determined.
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <string>
 7 #include <cstring>
 8 
 9 using namespace std;
10 
11 #define INF 1000000007
12 #define MAXN 30
13 #define MAX(a, b) (a > b ? a : b)
14 #define MIN(a, b) (a < b ? a : b)
15 
16 int n, m, pos1, pos2, pos3;
17 char ch[5];
18 int in[MAXN], ans[MAXN];
19 int g[MAXN][MAXN];
20 
21 int work()
22 {
23     int temp[MAXN], total = 0, idx = -1, flag = 0;
24     for (int i = 0; i < n; ++i)
25         temp[i] = in[i];
26     for (int i = 0; i < n; ++i)
27     {
28         int cnt = 0;
29         for (int j = 0; j < n; ++j)
30             if (temp[j] == 0) idx = j, cnt++;
31         if (cnt == 0) return 0;
32         if (cnt > 1) flag = 1;
33         temp[idx]--; ans[total++] = idx;
34         for (int j = 0; j < n; ++j)
35             if (g[idx][j]) temp[j]--;
36     }
37     if (flag) return -1;
38     return 1;
39 }
40 
41 int main()
42 {
43     while (~scanf("%d%d", &n, &m) && n+m!=0)
44     {
45         int flag = 0;
46         memset(g, 0, sizeof(g));
47         memset(in, 0, sizeof(in));
48         for (int i = 0; i < m; ++i)
49         {
50             scanf("%s", ch);
51             if (flag) continue;
52             g[ch[0]-'A'][ch[2]-'A'] = 1;
53             in[ch[2]-'A']++;
54             int ret = work();
55             if (ret == 0)
56             {
57                 printf("Inconsistency found after %d relations.
", i + 1);
58                 flag = 1;
59             }
60             else if (ret == 1)
61             {
62                 printf("Sorted sequence determined after %d relations: ", i + 1);
63                 for (int j = 0; j < n; ++j) printf("%c", ans[j]+'A');
64                 puts(".");
65                 flag = 1;
66             }
67         }
68         if (!flag) puts("Sorted sequence cannot be determined.");
69     }
70 
71     return 0;
72 }

View Code

3.The Cow Lexicon

 1 //先求出g[i][j]两点之间最少删除字符，然后DP，感觉测试数据应该比较弱，因为我1A了。。。
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <string>
 7 #include <cstring>
 8 
 9 using namespace std;
10 
11 #define INF 1000000007
12 #define MAXN 310
13 #define MAX(a, b) (a > b ? a : b)
14 #define MIN(a, b) (a < b ? a : b)
15 
16 char msg[MAXN];
17 int W, L;
18 int dis[MAXN];
19 char ch[610][MAXN];
20 int g[MAXN][MAXN];
21 
22 int main()
23 {
24     for (int i = 0; i < MAXN; ++i)
25         for (int j = i; j < MAXN; ++j)
26             g[i][j] = j-i+1;
27     scanf("%d%d", &W, &L);
28     scanf("%s", msg);
29     for (int i = 0; i < W; ++i) scanf("%s", ch[i]);
30     for (int i = 0; i < W; ++i)
31     {
32         for (int j = 0; j < L; ++j)
33         {
34             if (ch[i][0] == msg[j])
35             {
36                 int x = j, y = 0, cnt = 0;
37                 while (x < L && y < strlen(ch[i]))
38                 {
39                     if (msg[x] == ch[i][y]) x++, y++;
40                     else cnt++, x++;
41                 }
42                 if (y == strlen(ch[i]))
43                     g[j][x-1] = min(cnt, g[j][x-1]);
44             }
45         }
46     }
47     for (int i = 0; i < MAXN; ++i) dis[i] = i+1;
48     for (int i = 0; i < L; ++i)
49     {
50         int pre = i == 0 ? 0 : dis[i-1];
51         for (int j = i; j < L; ++j)
52             dis[j] = min(pre+g[i][j], dis[j]);
53     }
54     printf("%d
", dis[L-1]);
55 
56     return 0;
57 }

View Code

4.Word Pattern

 1 //水题
 2 class Solution {
 3 public:
 4     bool wordPattern(string pattern, string str) {
 5         vector<string> v;
 6         v.clear();
 7         string add = "";
 8         for (int i = 0; i < str.length(); ++i)
 9         {
10             if (str[i] == ' ')
11                 v.push_back(add), add = "";
12             else add += str[i];
13         }
14         if (add != "")v.push_back(add);
15         if (pattern.length() != v.size()) return false;
16         for (int i = 0; i < pattern.length(); ++i)
17         {
18             for (int j = i+1; j < pattern.length(); ++j)
19             {
20                 if (pattern[i] == pattern[j] && v[i] != v[j]) return false;
21                 if (pattern[i] != pattern[j] && v[i] == v[j]) return false;        
22             }
23         }
24         return true;
25     }
26 };

View Code

//关于图匹配的一些算法还是有点麻烦==。边学边做。。。

5.Strategic Game

 1 //最小顶点覆盖
 2 #include <iostream>
 3 #include <string>
 4 #include <cstdio>
 5 #include <cstring>
 6 #include <algorithm>
 7 #include <queue>
 8 #include <vector>
 9 #include <set>
10 #include <map>
11 #include <fstream>
12 #include <cstdlib>
13 #define NDEBUG
14 #include <cassert>
15 
16 using namespace std;
17 
18 #define INF 1000000007
19 #define MIN(a, b) (a > b ? b : a)
20 #define MAX(a, b) (a > b ? a : b)
21 #define MAXN 2005
22 
23 struct Edge
24 {
25     int v;
26     int next;    
27 };
28 
29 int cnt, n;
30 int vis[MAXN], link[MAXN], head[MAXN];
31 Edge edge[MAXN*MAXN];
32 
33 void init()
34 {
35     cnt = 0;
36     memset(head, -1, sizeof(head));
37 }
38 
39 void addEdge(int u, int v)
40 {
41     edge[cnt].v = v;
42     edge[cnt].next = head[u];
43     head[u] = cnt++;    
44 }
45 
46 int dfs(int u)
47 {
48     for (int e = head[u]; ~e; e = edge[e].next)
49     {
50         int v = edge[e].v;
51         if (!vis[v])
52         {
53             vis[v] = 1;
54             if (link[v] == -1 || dfs(link[v]))
55             {
56                 link[v] = u;
57                 return 1;
58             }
59         }
60     }
61     return 0;
62 }
63 
64 int match()
65 {
66     int ans = 0;
67     memset(link, -1, sizeof(link));
68     for (int i = 0; i < n; ++i)
69     {
70         memset(vis, 0, sizeof(vis));
71         if (dfs(i)) ans++;
72     }
73     return ans;
74 }
75 
76 int main()
77 {
78     while (~scanf("%d", &n))
79     {
80         init();
81         for (int i = 0; i < n; ++i)
82         {
83             int u, v, k;
84             scanf("%d:(%d)", &u, &k);
85             while (k--)
86             {
87                 scanf("%d", &v);
88                 addEdge(u, v);
89                 addEdge(v, u);
90             }
91         }
92         printf("%d
", match()/2);
93     }    
94     
95     return 0;
96 }

View Code

6.Machine Schedule

 1 //匈牙利算法，0的时候无需重启，所以处理的时候是从1开始的，而不是从0
 2 #include <iostream>
 3 #include <string>
 4 #include <cstdio>
 5 #include <cstring>
 6 #include <algorithm>
 7 #include <queue>
 8 #include <vector>
 9 #include <set>
10 #include <map>
11 #include <fstream>
12 #include <cstdlib>
13 #define NDEBUG
14 #include <cassert>
15 
16 using namespace std;
17 
18 #define INF 1000000007
19 #define MIN(a, b) (a > b ? b : a)
20 #define MAX(a, b) (a > b ? a : b)
21 #define MAXN 105
22 
23 int n, m, k;
24 int link[MAXN], vis[MAXN];
25 int edge[MAXN][MAXN];
26 
27 void init()
28 {
29     memset(edge, 0, sizeof(edge));    
30     memset(link, -1, sizeof(link));
31 }
32 
33 int dfs(int u)
34 {
35     for (int j = 1; j < m; ++j)
36     {
37         if (edge[u][j] && !vis[j])
38         {
39             vis[j] = 1;
40             if (link[j] == -1 || dfs(link[j]))
41             {
42                 link[j] = u;
43                 return 1;
44             }
45         }
46     }
47     return 0;    
48 }
49 
50 int match()
51 {
52     int ans = 0;
53     for (int i = 1; i < n; ++i)
54     {
55         memset(vis, 0, sizeof(vis));
56         ans += dfs(i);
57     }
58     return ans;
59 }
60 
61 int main()
62 {
63     while (~scanf("%d", &n) && n)
64     {
65         init();
66         scanf("%d%d", &m, &k);
67         int j, x, y;
68         for (int i = 0; i < k; ++i)
69         {
70             scanf("%d%d%d", &j, &x, &y);
71             edge[x][y] = 1;
72         }
73         printf("%d
", match());
74     }    
75     return 0;
76 }

View Code