HDU 5624 Reconstruction

正文索引 [隐藏]

题目翻译
题解
代码

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5624

题目翻译

http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=670&pid=1004

题解

首先很Naive的做法就是，枚举最小边，然后做最小生成树，这样会TLE。
我们想到可以动态做一个最小生成树，我们把所有边从大到小排序。
每次插入一条边
如果插入使树出现环，按照最小生成树的性质，我们应该删掉这个环上的费用最大的边，然后插入这条边。
如果插入不导致环的出现，那么直接插入即可。
然后用一个multiset，维护每次更新之后最大值和最小值的差即可。

代码

//while(true) RP++;
#include<cstdio>
#include<queue>
#include<set>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int Maxn=2000;
const int Maxm=15000;
int n,m;
struct EdgeNode{
    int u,v;
    int cost;
};
EdgeNode edge[Maxm+5];
struct Edge{
    int pre,nxt;
    int cost,u,v;
    Edge(){}
    Edge(int u0,int v0,int c0,int p0,int n0){
        u=u0;
        v=v0;
        cost=c0;
        pre=p0;
        nxt=n0;
    }
};
Edge e[Maxm*4+15];
int head[Maxn+5];
int nume=1;
inline void addEdge(int u,int v,int c){
    nume++;
    e[nume]=Edge(u,v,c,0,head[u]);
    e[head[u]].pre=nume;
    head[u]=nume;
    nume++;
    e[nume]=Edge(v,u,c,0,head[v]);
    e[head[v]].pre=nume;
    head[v]=nume;
}
inline void deleteEdge(int now){
    if (e[now].pre==0){
        head[e[now].u]=e[now].nxt;
        e[e[now].nxt].pre=0;
    }else{
        e[e[now].pre].nxt=e[now].nxt;
        e[e[now].nxt].pre=e[now].pre;
    }
    if (e[now^1].pre==0){
        head[e[now^1].u]=e[now^1].nxt;
        e[e[now^1].nxt].pre=0;
    }else{
        e[e[now^1].pre].nxt=e[now^1].nxt;
        e[e[now^1].nxt].pre=e[now^1].pre;
    }
}
int father[Maxn+5];
int pre[Maxn+5];
bool dfsDown(int x,int fa,int dst){
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v;
        if (v==fa) continue;
        father[v]=x;
        pre[v]=i;
        if (dst==v) return true;
        if (dfsDown(v,x,dst)) return true;
    }
    return false;
}
int maxCost,edgeIndex;
void dfsUp(int x,int dst){
    while(x!=dst){
        if (edgeIndex==-1 || maxCost<e[pre[x]].cost){
            edgeIndex=pre[x];
            maxCost=e[pre[x]].cost;
        }
        x=father[x];
    }
}
inline bool cmp(EdgeNode a,EdgeNode b){
    if (a.cost>b.cost) return true;
    return false;
}
multiset<int> EdgeCost;
inline void solve(int T){
    memset(head,0,sizeof(head));
    nume=1;
    EdgeCost.clear();
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
        scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].cost);
    int Ans=-1;
    int cnt=n;
    sort(edge+1,edge+m+1,cmp);
    for (int i=1;i<=m;i++){
        int now=0;
        //printf("? %d - %d\n",edge[i].u,edge[i].v);
        if (!dfsDown(edge[i].u,0,edge[i].v)){
            //printf("Not Find\n");
            addEdge(edge[i].u,edge[i].v,edge[i].cost);
            EdgeCost.insert(edge[i].cost);
            cnt--;
        }else{
            //printf("Find\n");
            edgeIndex=-1;
            dfsUp(edge[i].v,edge[i].u);
            deleteEdge(edgeIndex);
            addEdge(edge[i].u,edge[i].v,edge[i].cost);
            EdgeCost.insert(edge[i].cost);
            EdgeCost.erase(e[edgeIndex].cost);
        }
        now=abs((*EdgeCost.begin())-(*EdgeCost.rbegin()));
        //if (cnt==1) printf("%d\n",Ans);
        if (cnt==1) if (Ans==-1 || now<Ans) Ans=now;
    }
    printf("%d\n",Ans);
}
int main(){
    int T=0;
    while(scanf("%d",&T)!=EOF)
        for (int i=1;i<=T;i++)
            solve(i);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

//while(true) RP++;

#include<cstdio>

#include<queue>

#include<set>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int Maxn=2000;

const int Maxm=15000;

int n,m;

struct EdgeNode{

int u,v;

int cost;

};

EdgeNode edge[Maxm+5];

struct Edge{

int pre,nxt;

int cost,u,v;

Edge(){}

Edge(int u0,int v0,int c0,int p0,int n0){

u=u0;

v=v0;

cost=c0;

pre=p0;

nxt=n0;

}

};

Edge e[Maxm*4+15];

int head[Maxn+5];

int nume=1;

inline void addEdge(int u,int v,int c){

nume++;

e[nume]=Edge(u,v,c,0,head[u]);

e[head[u]].pre=nume;

head[u]=nume;

nume++;

e[nume]=Edge(v,u,c,0,head[v]);

e[head[v]].pre=nume;

head[v]=nume;

}

inline void deleteEdge(int now){

if (e[now].pre==0){

head[e[now].u]=e[now].nxt;

e[e[now].nxt].pre=0;

}else{

e[e[now].pre].nxt=e[now].nxt;

e[e[now].nxt].pre=e[now].pre;

}

if (e[now^1].pre==0){

head[e[now^1].u]=e[now^1].nxt;

e[e[now^1].nxt].pre=0;

}else{

e[e[now^1].pre].nxt=e[now^1].nxt;

e[e[now^1].nxt].pre=e[now^1].pre;

}

int father[Maxn+5];

int pre[Maxn+5];

bool dfsDown(int x,int fa,int dst){

for (int i=head[x];i;i=e[i].nxt){

int v=e[i].v;

if (v==fa) continue;

father[v]=x;

pre[v]=i;

if (dst==v) return true;

if (dfsDown(v,x,dst)) return true;

}

return false;

}

int maxCost,edgeIndex;

void dfsUp(int x,int dst){

while(x!=dst){

if (edgeIndex==-1 || maxCost<e[pre[x]].cost){

edgeIndex=pre[x];

maxCost=e[pre[x]].cost;

}

x=father[x];

}

inline bool cmp(EdgeNode a,EdgeNode b){

if (a.cost>b.cost) return true;

return false;

}

multiset<int> EdgeCost;

inline void solve(int T){

memset(head,0,sizeof(head));

nume=1;

EdgeCost.clear();

scanf("%d%d",&n,&m);

for (int i=1;i<=m;i++)

scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].cost);

int Ans=-1;

int cnt=n;

sort(edge+1,edge+m+1,cmp);

for (int i=1;i<=m;i++){

int now=0;

//printf("? %d - %d\n",edge[i].u,edge[i].v);

if (!dfsDown(edge[i].u,0,edge[i].v)){

//printf("Not Find\n");

addEdge(edge[i].u,edge[i].v,edge[i].cost);

EdgeCost.insert(edge[i].cost);

cnt--;

}else{

//printf("Find\n");

edgeIndex=-1;

dfsUp(edge[i].v,edge[i].u);

deleteEdge(edgeIndex);

addEdge(edge[i].u,edge[i].v,edge[i].cost);

EdgeCost.insert(edge[i].cost);

EdgeCost.erase(e[edgeIndex].cost);

}

now=abs((*EdgeCost.begin())-(*EdgeCost.rbegin()));

//if (cnt==1) printf("%d\n",Ans);

if (cnt==1) if (Ans==-1 || now<Ans) Ans=now;

}

printf("%d\n",Ans);

}

int main(){

int T=0;

while(scanf("%d",&T)!=EOF)

for (int i=1;i<=T;i++)

solve(i);

return 0;

}

WNJXYKの博客

喂你脚下有坑