题意：
给一个N个点的完全图 有边权
然后你可以删K条边，让剩下的图的最短路最长
题解：
发现K很小，暴力搜一下，
再想一下，只搜当前最短路上的边就可以
复杂度未知，本地跑的挺快，然后交就完事了（引自zbr）
#include<bits/stdc++.h> #define rep(i,a,n) for(int i=a;i<=n;++i) #define per(i,a,n) for(int i=n;i>=a;--i) #define pb push_back #define fi first #define se second #define io std::ios::sync_with_stdio(false) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int P = 1e9+7, INF = 0x3f3f3f3f; ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; } ll qpow(ll a,ll n) { ll r=1%P; for (a%=P; n; a=a*a%P,n>>=1)if(n&1)r=r*a%P; return r; } const int maxn=51; int n; int k; vector<int> G[maxn]; int d[maxn]; int fa[maxn]; int dis[maxn][maxn]; void djs(int s) { priority_queue<pii,vector<pii>,greater<pii> > que; memset(d,INF,sizeof(d)); d[s]=0; que.push(make_pair(0,s)); while(!que.empty()) { pii p=que.top(); que.pop(); int v=p.second; if(d[v]<p.first)continue; for(int i=0; i<G[v].size(); i++) { int to=G[v][i]; if(d[to]>d[v]+dis[to][v]) { d[to]=d[v]+dis[to][v]; fa[to]=v; que.push(make_pair(d[to],to)); } } } } int ans=0; void dfs(int i) { djs(1); if(i==k+1) { ans=max(ans,d[n]); return ; } int x,y; int cur=n; while(1) { x=cur; y=fa[cur]; int temp=dis[x][y]; dis[x][y]=INF; dis[y][x]=INF; dfs(i+1); dis[x][y]=temp; dis[y][x]=temp; djs(1); cur=fa[cur]; if(cur==1) break; } } int main() { int t; cin>>t; while(t--) { ans=0; cin>>n>>k; for(int i=1; i<=n; i++) G[i].clear(); for(int i=1; i<=(n-1)*n/2; i++) { int x,y,w; cin>>x>>y>>w; G[x].push_back(y); G[y].push_back(x); dis[x][y]=w; dis[y][x]=w; } dfs(1); cout<<ans<<endl; } }
这个代码比赛时候过了，然后看评论说TLE，然后我又交了一发确实T了 ，难道是赛后加强了数据？
看了看代码发现还能改进一下。
这份代码不会T，每次记录一次father就行了，就不用每次跑一次最短路了
#include<bits/stdc++.h> #define rep(i,a,n) for(int i=a;i<=n;++i) #define per(i,a,n) for(int i=n;i>=a;--i) #define pb push_back #define fi first #define se second #define io std::ios::sync_with_stdio(false) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int P = 1e9+7, INF = 0x3f3f3f3f; ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; } ll qpow(ll a,ll n) { ll r=1%P; for (a%=P; n; a=a*a%P,n>>=1)if(n&1)r=r*a%P; return r; } const int maxn=51; int n; int k; vector<int> G[maxn]; int d[maxn]; int fa[maxn]; int dis[maxn][maxn]; void djs(int s) { priority_queue<pii,vector<pii>,greater<pii> > que; memset(d,INF,sizeof(d)); d[s]=0; que.push(make_pair(0,s)); while(!que.empty()) { pii p=que.top(); que.pop(); int v=p.second; if(d[v]<p.first)continue; for(int i=0; i<G[v].size(); i++) { int to=G[v][i]; if(d[to]>d[v]+dis[to][v]) { d[to]=d[v]+dis[to][v]; fa[to]=v; que.push(make_pair(d[to],to)); } } } } int ans=0; void dfs(int i) { djs(1); if(i==k+1) { ans=max(ans,d[n]); return ; } int x,y; int cur=n; int faa[maxn]; for(int i=1;i<=n;i++) { faa[i]=fa[i]; } while(1) { x=cur; y=faa[cur]; int temp=dis[x][y]; dis[x][y]=INF; dis[y][x]=INF; dfs(i+1); dis[x][y]=temp; dis[y][x]=temp; //djs(1); cur=faa[cur]; if(cur==1) break; } } int main() { int t; cin>>t; while(t--) { ans=0; cin>>n>>k; for(int i=1; i<=n; i++) G[i].clear(); for(int i=1; i<=(n-1)*n/2; i++) { int x,y,w; cin>>x>>y>>w; G[x].push_back(y); G[y].push_back(x); dis[x][y]=w; dis[y][x]=w; } dfs(1); cout<<ans<<endl; } }