终于AC了，大概在8月份就会做这道题了，一直没有去写（bs下自己）。
拖了好久昨天下定决心说一定要把这道题AC了（pku1639），于是就开始写，结果一下从18：00wa到21：30.。。。都怨操作系统老师，我都在睡觉了她讲课还把我搞的头疼了一天…
今天起来决定重写,之前写的那个实在是太烂了.
精神好了干什么都顺利,在经过几个莫名其妙的小错误后,终于A了…真难…不过真爽哈哈
由此也发现我驾驭代码的能力还是不够强…超过200的代码就不是很有信心了…
最小度限制生成树在黑书上有证明和解答,算是个很经典的问题了.是由最小生成树派生出来的一个近贪心的算法.当然这里是指只对一个顶点的度数有限制,如果是所有的点都有限制的话,那就是N-P hard的了.
我的处理方法是 先对除去限制点以外的点求个最小生成树或森林,然后把限制点出来的边从小到大枚举,对现有的最小生成森林中的每个连通块选择一个最小的边相连.这里的复杂度都是比较小的.最后一步就麻烦了,对于尚未使用的限制点出来的边,如果它对生成树的长度减少有帮助,就把它加上,把能删去的删去.
怎么处理呢?对每次添删操作,用1边dfs搜出(O(n+m))对于每个点,它到限制点之间的最长的边(长度设为X(i)),然后就枚举限制点出来的边,选择最好的(lengh(0,i)-x(i)最小的).
如此进行到限制点连的边等于限制度数或者lengh(0,i)-x(i)>=0,即此操作无法使生成树更优
不过我还真不知道原来问什么会wa…
程序:
1
#include<iostream>
2using namespace std;
3
4
struct adj 
{
5
int st,ed,ll;
6 adj *pe;
7
};
8adj *node[30];
9adj bn[400],maxl[100],now[100],head[100];
10
11int vn,hn,vm;
12int father[30],hx[30],use[30];
13char name[30][20];
14int find(char s[30])
15{
16 int i;
17 for(i=0;i<vn;i++)
18 if(strcmp(s,name[i])==0)
19 return i;
20 for(i=0;s[i];i++)
21 name[vn][i]=s[i];
22 name[vn][i]=s[i];
23 vn++;
24 return vn-1;
25}
26
27int insert(int a,int b,int c)
28{
29 adj *p;
30 p=node[a];
31 node[a]=(adj*)malloc(sizeof(adj));
32 node[a]->st=a;
33 node[a]->ed=b;
34 node[a]->ll=c;
35 node[a]->pe=p;
36 return 0;
37}
38
39int findfather(int x)
40{
41 if(x!=father[x])
42 father[x]=findfather(father[x]);
43 return father[x];
44}
45
46int del(int a,int b)
47{
48 adj *p;
49 p=node[a];
50 if(node[a]->ed==b)
51
{
52 node[a]=node[a]->pe;
53 return 0;
54
}
55 while(p->pe!=NULL)
56 {
57 if(p->pe->ed==b)
58 {
59 p->pe=p->pe->pe;
60 return 0;
61 }
62 p=p->pe;
63 }
64 return 0;
65}
66
67int cmp(adj p,adj q)
68{
69 return p.ll<q.ll;
70}
71
72int dfs(int x,int a,int b,int l)
73{
74 use[x]=1;
75 int aa,bb,ll;
76 adj *p;
77 p=node[x];
78 while(p!=NULL)
79 {
80 if(use[p->ed])
81 {
82 p=p->pe;
83 continue;
84 }
85 if(p->ll>=l)
86 {
87 aa=x;
88 bb=p->ed;
89 ll=p->ll;
90 }
91 else
92 {
93 aa=a;
94 bb=b;
95 ll=l;
96 }
97 maxl[p->ed].st=aa;
98 maxl[p->ed].ed=bb;
99 maxl[p->ed].ll=ll;
100 dfs(p->ed,aa,bb,ll);
101 p=p->pe;
102 }
103 return 0;
104}
105
106
107int main()
108{
109 int i,j,k,n,m,a,b,c,num,key;
110 char s1[30],s2[30];
111 int res;
112 memset(node,0,sizeof(node));
113 memset(name,0,sizeof(name));
114 name[0][0]='P',name[0][1]='a',
115 name[0][2]='r',name[0][3]='k',
116 name[0][4]='\0';
117 scanf("%d\n",&m);
118 vn=1;hn=0;vm=0;res=0;
119 for(i=0;i<m;i++)
120 {
121 scanf("%s %s %d\n",s1,s2,&c);
122 a=find(s1);
123 b=find(s2);
124 if(a==0||b==0)
125 {
126 head[hn].st=0;
127 head[hn].ed=a+b;
128 head[hn++].ll=c;
129 continue;
130 }
131 bn[vm].st=a;
132 bn[vm].ed=b;
133 bn[vm++].ll=c;
134 }
135 scanf("%d\n",&key);
136 sort(bn,bn+vm,cmp);
137 for(i=0;i<30;i++)
138 father[i]=i;
139 for(i=0;i<vm;i++)
140 {
141 a=findfather(bn[i].st);
142 b=findfather(bn[i].ed);
143 if(a!=b)
144 {
145 father[a]=b;
146 res+=bn[i].ll;
147 insert(bn[i].st,bn[i].ed,bn[i].ll);
148 insert(bn[i].ed,bn[i].st,bn[i].ll);
149 }
150 }
151 for(i=1;i<vn;i++)
152 findfather(i);
153
154
155 sort(head,head+hn,cmp);
156 memset(hx,0,sizeof(hx));
157 for(i=0,num=0;i<hn;i++)
158 {
159 a=findfather(head[i].ed);
160 if(!hx[a])
161 {
162 res+=head[i].ll;
163 insert(0,head[i].ed,head[i].ll);
164 insert(head[i].ed,0,head[i].ll);
165 head[i].st=-1;
166 hx[a]=1;
167 num++;
168 }
169 }
170 for(i=0,k=0;i<hn;i++)
171 {
172 if(head[i].st!=-1)
173 now[k++]=head[i];
174 }
175 hn=k;
176 while(1)
177 {
178 if(num>=key) break;
179 memset(maxl,-1,sizeof(maxl));
180 memset(use,0,sizeof(use));
181 dfs(0,-1,-1,-10);
182 for(i=k=0;i<hn;i++)
183 {
184 if(now[k].st==-1||
185 (now[i].st!=-1
186 &&now[i].ll-maxl[now[i].ed].ll
187 <now[k].ll-maxl[now[k].ed].ll))
188 k=i;
189 }
190 if(now[k].st==-1||now[k].ll-maxl[now[k].ed].ll>=0)
191 break;
192 insert(0,now[k].ed,now[k].ll);
193 insert(now[k].ed,0,now[k].ll);
194 res+=now[k].ll-maxl[now[k].ed].ll;
195 del(maxl[now[k].ed].st,maxl[now[k].ed].ed);
196 del(maxl[now[k].ed].ed,maxl[now[k].ed].st);
197 now[k].st=-1;
198 num++;
199 }
200
201 printf("Total miles driven: %d\n",res);
202 return 0;
203}
204
205