标签：char 多校3 can php div sdi void ret 枚举
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6797
题目大意：n个点的完全图，要求删k条边，求删完k条边后的最短路的最大值。
3≤n≤50,1≤k≤min(n−2,5) 边权为[ 1 , 10^4 ] 的随机数
题解：
删的边一定在当前的最短路上，跑一遍dijstra，暴力枚举删最短路上的哪条边，然后进行下一轮删边。
在删完k条边时，跑一遍用当前的dis[n]更新ans。
ps：1. 记录边的时候开一个pre记录每个点前面的结点，然后能顺着找到路径。
2.因为有好几轮记录，但是是按深度dfs的，最多有k层，要把pre开成二维数组，最多 pre[k][n]就可以了。 【一开始没想到是按深度的，把每轮dijstra的pre都记录了，pre开的非常大，有pre[1000000][50],也没炸】
官方标程【觉得写得非常的简洁，先放出来】：
1.pre不用开大
2.稠密图直接写n^2的dijstra，不用堆优化
1 #include 2 const int N=55,K=15,inf=100000000;
3 int Case,n,m,i,j,x,y,z,g[N][N],d[N],f[K][N],v[N],ans;
4 void dfs(int m){
5 int i,j,k;
6 for(i=1;i0;
7 for(d[1]=0,i=1;i){
8 k=0;
9 for(j=1;jif(!v[j])if(!k||d[j]j;
10 v[k]=1;
11 for(j=1;jif(!v[j]&&d[k]+g[k][j]d[j]){
12 d[j]=d[k]+g[k][j];
13 f[m][j]=k;
14 }
15 }
16 if(!m){
17 if(ansd[n];
18 return;
19 }
20 for(i=n;i!=1;i=j){
21 j=f[m][i];
22 k=g[i][j];
23 g[i][j]=g[j][i]=inf;
24 dfs(m-1);
25 g[i][j]=g[j][i]=k;
26 }
27 }
28 int main(){
29 scanf("%d",&Case);
30 while(Case--){
31 scanf("%d%d",&n,&m);
32 for(i=1;ifor(j=1;j0:inf;
33 for(i=1;i1)/2;i++){
34 scanf("%d%d%d",&x,&y,&z);
35 g[x][y]=g[y][x]=z;
36 }
37 ans=0;
38 dfs(m);
39 printf("%d\n",ans);
40 }
41 }
2.个人ac代码
弊端：
1.pre数组开的太大
2.堆优化dijstra比较冗余
1 #include 2 using namespace std;
3 typedef long long ll;
4 const int INF = 0x3f3f3f3f;
5 const int MAXN = 55,mu=1000000;
6 const int MAXM = 3025;
7 int pre[mu][MAXN],mp[MAXN][MAXN],t[MAXM],d[MAXN],tot;
8
9 inline int read() {
10 int x = 0, ff = 1; char ch = getchar();
11 while(!isdigit(ch)) {
12 if(ch == ‘-‘) ff = -1;
13 ch = getchar();
14 }
15 while(isdigit(ch)) {
16 x = (x 1) + (x 3) + (ch ^ 48);
17 ch = getchar();
18 }
19 return x * ff;
20 }
21 int n, m, k;
22 struct love
23 {
24 int num, d;
25 };
26
27 bool operator (love a, love b)
28 {
29 return a.d > b.d;
30 }
31 /*used 是否使用过结点
32 d 到结点1的距离
33 */
34 priority_queue q;
35 bool used[MAXN];
36 void dijkstra()
37 {
38 memset(used,0,sizeof(used));
39 for(int i=0;iINF;
40 int s=1;
41 q.push((love){s, 0});
42 d[s] = 0;
43 used[s] = 1;
44 while (!q.empty())
45 {
46 int now = q.top().num;
47 q.pop();
48 used[now] = 1;
49 for (int i = 1; i )
50 {
51 if (d[i] > d[now] + mp[now][i])
52 {
53 d[i] = d[now] + mp[now][i];
54 pre[tot][i]=now;
55 if (!used[i])
56 {
57 q.push((love){i, d[i]});
58 }
59 }
60 }
61 }
62 }
63 int totans;
64
65 void dfs(int cnt){
66 tot++;
67 int num=tot;
68 dijkstra();
69 if(cnt==k+1){
70 totans=max(totans,d[n]);
71 return;
72 }
73 int uu=n;
74 while(uu!=1){
75 //暴力枚举删最短路上的哪条边
76 // printf("uu: %d pre[uu]: %d \n",uu,pre[uu]);
77 int gg=pre[num][uu];
78 int tmp=mp[uu][gg];
79 mp[uu][gg]=INF;
80 mp[gg][uu]=INF;
81 dfs(cnt+1);//搜完之后要回溯
82 mp[uu][gg]=tmp;
83 mp[gg][uu]=tmp;
84 uu=gg;
85 //cout
86 }
87 }
88 int main(){
89 int tt;
90 scanf("%d",&tt);
91 while(tt--){
92 // cout
93 n=read();
94 k=read();
95 m=(n-1)*n/2;
96 totans=0;
97 for(int i = 1; i i) {
98 int x,y,v;
99 x = read(); y = read(); v = read();
100 mp[x][y]=mp[y][x]=v;
101 }
102 dfs(1);
103 printf("%d\n",totans);
104 }
105 return 0;
106 }
107 /*
108 10
109 5 10 5
110 1 2 2990
111 1 3 2414
112 1 4 4018
113 1 5 6216
114 2 3 9140
115 2 4 4169
116 2 5 550
117 3 4 6618
118 3 5 3206
119 4 5 105
120
121 */
[hdu-6797]Tokitsukaze and Rescue 爆搜枚举+dijstra最短路 2020多校3
标签：char 多校3 can php div sdi void ret 枚举
原文地址：https://www.cnblogs.com/conver/p/13394597.html