学步园

 

Zoj 3613 Wormhole Transport (综合_斯坦纳树)

分类： 全部博客 ACM_动态规划(DP) ACM_数据结构 ACM_图论系列2012-09-05
00:16 462人阅读 评论(0) 收藏 举报

treestructnulloutputinputc

题目链接:  http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3613

题目大意: 给定一张图有n个顶点，某些点有工厂，某些点有资源，每个资源可以供应给一个工厂，有m条无向边，边有边权。已知有资源的点不超过4个，有工厂的点也不超过4个，问选择若干条边如何使有资源工厂的工厂最多，当数量一样多时输出最小权值。n <= 200, m <= 5000.

解题思路: 很一般的斯坦纳树。这类问题模型一般是固定的，就比如这题和Hdu 4085就十分相像，但这题会略微复杂点。首先是找有工厂和有资源的点然后先存起来，k = 工厂点数+资源点数,总状态为1<<k.然后这题的工厂数应该要大等于资源数，这个很显然，这样的话判断转改合法不合法就要判断着两个数量的关系了。

测试数据:

Input:
2
0 1
1 0
1
1 2 3

2
1 1
1 1
1
1 2 3

4
2 1
1 0
0 1
1 1
3
1 2 3
2 3 4
3 4 4

4
0 1
0 1
1 0
1 0
2
1 3 1
2 4 1

OutPut:
1 3
2 0
3 4
2 2

C艹代码:

[cpp] view
plaincopy

1. #include <stdio.h>  
2. #include <string.h>  
3. #include <queue>  
4. using namespace std;  
5. #define MIN 1000  
6. #define MAX 5100  
7. #define INF (1<<29)  
8. #define min(a,b) ((a)<(b)?(a):(b))  
9.   
10.   
11. struct planet{  
12.   
13.     int a,b;  
14. }arr[MIN];  
15. struct node {  
16.   
17.     int v,len;  
18.     node *next;  
19. }*head[MAX*2],tree[MAX*2];  
20. queue<int> qu;  
21. bool in[MIN][MIN];  
22. int k,res[MIN],tot,fac[MIN];  
23. int n,m,ans,ansi,ptr,st[MIN],nn;  
24. int orik,cost[MIN][MIN],dp[MIN];  
25.   
26.   
27. void Initial() {  
28.   
29.     int i,j,t;  
30.   
31.   
32.     ptr = 0,orik = k;  
33.     memset(st,0,sizeof(st));  
34.     memset(in,false,sizeof(in));  
35.     memset(head,NULL,sizeof(head));  
36.     for (i = 0; i < tot; ++i)  
37.         res[k++] = fac[i];  
38.   
39.       
40.     nn = 1 << k;  
41.     for (i = 0; i < nn; ++i)   
42.         for (j = 0; j < n; ++j)  
43.             cost[j][i] = INF;  
44.   
45.   
46.     for (i = 0; i < k; ++i)  
47.         st[res[i]] = 1<<i,cost[res[i]][st[res[i]]] = 0;  
48. }  
49. void AddEdge(int a,int b,int c) {  
50.   
51.     tree[ptr].v = b,tree[ptr].len = c;  
52.     tree[ptr].next = head[a],head[a] = &tree[ptr++];  
53. }  
54. void Spfa() {  
55.   
56.     while (!qu.empty()) {  
57.   
58.         int j = qu.front() / MAX;  
59.         int i = qu.front() % MAX;  
60.         qu.pop(),in[j][i] = false;  
61.   
62.   
63.         node *p = head[j];  
64.         while (p != NULL) {  
65.   
66.             int v = p->v,nst = i | st[v];  
67.             if (cost[j][i] + p->len < cost[v][nst]) {  
68.   
69.                 cost[v][nst] = cost[j][i] + p->len;  
70.                 if (nst == i && !in[v][nst])  
71.                     qu.push(v*MAX+nst),in[v][nst] = true;  
72.             }  
73.             p = p->next;  
74.         }  
75.     }  
76. }  
77. void Steiner_Tree() {  
78.   
79.     int i,j,t,s;  
80.     for (i = 0; i < nn; ++i) {  
81.   
82.         for (j = 0; j < n; ++j) {  
83.               
84.             if (st[j] && !(st[j] & i)) continue;   
85.             for (t = (i-1)&i; t; t = (t-1)& i)   
86.                 cost[j][i] = min(cost[j][i],cost[j][t|st[j]]+cost[j][(i-t)|st[j]]);  
87.             if (cost[j][i] != INF) qu.push(j*MAX+i),in[j][i] = true;      
88.         }  
89.         Spfa();  
90.     }  
91. }  
92. int Check(int st) {  
93.   
94.     int i,cnt = 0;  
95.     for (i = 0; i < orik; ++i)  
96.         if (st & (1<<i)) cnt++;  
97.     for (i = orik; i < k; ++i)  
98.         if (st & (1<<i)) cnt -= arr[fac[i-orik]].a;  
99.     return cnt <= 0;  
100. }  
101. void Solve_DP() {  
102.   
103.     int i,j,t;  
104.     for (i = 0; i < nn; ++i) {  
105.   
106.         dp[i] = INF;  
107.         for (j = 0; j < n; ++j)  
108.             dp[i] = min(dp[i],cost[j][i]);  
109.     }  
110.   
111.   
112.     for (i = 0; i < nn; ++i)  
113.         if (Check(i))for (t = (i-1)&i; t; t = (t-1)&i)  
114.             if (Check(t)&&Check(i-t)) dp[i] = min(dp[i],dp[t]+dp[i-t]);  
115.     for (i = 0; i < nn; ++i)  
116.         if (dp[i] != INF && Check(i)){  
117.   
118.             int cnt = 0;  
119.             for (j = 0; j < orik; ++j)  
120.                 if (i & (1<<j)) cnt++;  
121.             if (cnt > ans) ans = cnt,ansi = dp[i];  
122.             else if (cnt == ans && ansi > dp[i]) ansi = dp[i];  
123.         }  
124. }  
125.   
126.   
127. int main()  
128. {  
129.     int i,j,a,b,c,num;  
130.   
131.   
132.     while (scanf("%d",&n) != EOF) {  
133.   
134.         ans = ansi = 0;  
135.         num = k = tot = 0;  
136.         for (i = 0; i < n; ++i) {  
137.   
138.             scanf("%d%d",&arr[i].a,&arr[i].b);  
139.             if (arr[i].a && arr[i].b)  
140.                 num++,arr[i].a--,arr[i].b--;  
141.             if (arr[i].a) fac[tot++] = i;  
142.             if (arr[i].b) res[k++] = i;  
143.         }  
144.           
145.   
146.         Initial();  
147.         scanf("%d",&m);  
148.         for (i = 0; i < m; ++i) {  
149.   
150.             scanf("%d%d%d",&a,&b,&c);  
151.             a--,b--;  
152.             AddEdge(a,b,c),AddEdge(b,a,c);  
153.         }  
154.           
155.   
156.         Steiner_Tree();  
157.         Solve_DP();  
158.         printf("%d %d\n",ans+num,ansi);  
159.     }  
160. }