【题意】
给出N个点，M条边，问这N个点形成的生成树的最大权值边-最小权值边的最小值
Input
The input consists of several test cases, separated by single blank lines. Each test case begins with a
line containing the integer n (2 ≤ n ≤ 350), the number of doors in the building. The following line
contains another integer, m (n − 1 ≤ m ≤ n(n − 1)/2), the number of sensors in the network. The
test case finishes with m lines containing a description of each of the m sensors. The i-th of those lines
contains three integers, a (0 ≤ a ≤ n−1), b (0 ≤ b ≤ n−1) and w (1 ≤ w ≤ 2
15), in that order. Integers
a and b represent the pair of doors controlled by the i-th sensor, and w its recommended voltage. You
can safely assume that there are no two sensors controlling the same two doors.
The input will finish with a line containing ‘0’.
Output
For each case, your program should output a line containing the minimum margin of an admissible
subset of the sensors.
Sample Input
3
3
0 1 220
1 2 120
2 0 160
4
5
2 3 80
1 3 80
0 1 180
2 1 200
3 0 140
0
Sample Output
40
60
【分析】
是Uva1395的进化版。
数据范围大了一点点，不过之前的方法也是够慢的，m^2。
总结来说，生成树问题其实就是有一棵最小生成树，然后你sm乱枚举一些东西，然后在最小生成树上搞啊搞。。【难道不是么？？..
最喜欢就是加一条边弄一个环然后在环上面又删一条边，就是没add边的时候两个点之间唯一路径上的边的权值求最值。
这题就是这样啦。
先排序，加边，考虑一下加下去的边是否会形成环，如果形成环的话，就把环内的最小边去掉（因为最长边就是现在ADD的那条边，如果要苗条就让边最小尽量大），然后重新求这棵新的生成树的最小边。等到生成树形成的时候，因为添加进去的新边的权值肯定是最大值的，所以只要只减去之前维护一个的最小值就可以了。
然后，求路径最小边还有找最短边都是O（n）暴力的。
总时间复杂度：O（nm）
之前的方法复杂度是O（m^2）,嗯，很多恶心题就是完全图，如果是完全图的话，这样的方法无疑是更优的。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Maxn 410
#define INF 0xfffffff int n,m; struct node
{
int x,y,c;
}t[Maxn*Maxn]; bool cmp(node x,node y) {return x.c<y.c;}
int mymin(int x,int y) {return x<y?x:y;} int fa[Maxn]; bool vis[Maxn];
int get_lca(int now)
{
int x=t[now].x,y=t[now].y,ans=;
for(int i=;i<=n;i++) vis[i]=;
while(x!=fa[x]) vis[x]=,x=fa[x]; vis[x]=;
while(y!=fa[y])
{
if(vis[y]) {ans=y;break;}
y=fa[y];
}
if(ans==&&vis[y]) ans=y;
// while(x!=fa[x]) vis[x]=0,x=fa[x]; vis[x]=0;
return ans;
} int dis[Maxn],mn,cnt;
void ffind(int now)
{
int x=t[now].x,y=t[now].y;
// if(fa[x]!=fa[y]) return;
int lca=get_lca(now);
if(lca==) return;
int k=INF,kv;
while(x!=lca)
{
if(dis[x]<k)
{
k=dis[x];
kv=x;
}
x=fa[x];
}
while(y!=lca)
{
if(dis[y]<k)
{
k=dis[y];
kv=y;
}
y=fa[y];
}
fa[kv]=kv,dis[kv]=;
mn=INF;
for(int i=;i<=n;i++) if(fa[i]!=i)
{
mn=mymin(mn,dis[i]);
}
cnt--;
} void add(int now)
{
int x=t[now].x,y=t[now].y,c=t[now].c;
if(fa[x]==fa[y]) return;
if(fa[x]==x) fa[x]=y,dis[x]=c;
else if(fa[y]==y) fa[y]=x,dis[y]=c;
else
{
int xx=x,u=fa[x],dd=dis[x];
while(x!=u)
{
int nu=fa[u],nd=dis[u];
fa[u]=x;
dis[u]=dd;
x=u;u=nu;dd=nd;
}
fa[xx]=y;dis[xx]=c;
}
mn=mymin(mn,c);
cnt++;
} int main()
{
while()
{
scanf("%d",&n);
if(n==) break;
scanf("%d",&m);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].c);
t[i].x++;t[i].y++;
}
sort(t+,t++m,cmp);
cnt=;
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++) fa[i]=i;
mn=INF;
memset(dis,,sizeof(dis));
int ans=INF;
for(int i=;i<=m;i++)
{
ffind(i);
add(i);
if(cnt==n-) ans=mymin(ans,t[i].c-mn);
}
printf("%d\n",ans);
}
return ;
}
WC这题代码把LA3887 A了！！！！
2016-11-02 09:52:33
--------------------------------------------------------------------------
突然发现这题是删边模版？