# re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解 2011-09-04 19:08 PWK

补上1005题目思路，在这题的思路是对点进行割边的缩点从构图，如果2点2连通，那么他们连通的边是不能破坏的。能破坏的只有割边。由void DFS(int x,int farther) ，void Set_Color(int x)完成。完成后成为一棵树。之后就是博弈问题啦，做完敌人，他们要找到一条链，使得能尽量多的删除最小的边。不能删除的最小边权值则是这题的解。删除最小的边的方法是以最小边的两个点为根，分别构建树，树形DP，求节点下面的哪条路有最小边，找到不走的边的最小权值。输出。
#include <iostream>
#include <vector>
using namespace std;
#define maxn 10005
int MinN(int x,int y) {return x<y?x:y;}
struct node{int v,w;};
vector<node> map[maxn],newmap[maxn];
int DFn[maxn]; //深搜时节点的访问顺序
int low[maxn]; //存放当前接点不经过其父亲节点能够访问DFn值最小的节点
int color[maxn];
int dp[maxn];
int index;
int n,m,q;
int minu,minv,minw;
bool done[maxn];


void DFS(int x,int farther)
{
int i;
DFn[x]=low[x]=index++;//赋初值
for(i=0;i<map[x].size();i++)
{
if(!DFn[map[x][i].v])
{
DFS(map[x][i].v,x);
low[x]=MinN(low[x],low[map[x][i].v]);//检查子节点能返回的最早的祖先
}
else if(farther!=map[x][i].v)
low[x]=MinN(low[x],DFn[map[x][i].v]);//检查从自身出发的后向边（无向图中没有横叉边）
}
}
void Set_Color(int x)//染色，同一双连通分量内的节点用一种颜色
{
int i;
node tmp;
for(i=0;i<map[x].size();i++)
{
if(!color[map[x][i].v])
{
if(low[map[x][i].v]>DFn[x]) //(node,map[node][i])是割边
{
color[map[x][i].v]=index++;
tmp.v=color[map[x][i].v];tmp.w=map[x][i].w;
newmap[color[x]].push_back(tmp);
tmp.v=color[x];
newmap[color[map[x][i].v]].push_back(tmp);
if(map[x][i].w<minw)
{
minw=map[x][i].w;
minu=color[x];
minv=color[map[x][i].v];
}
}
else color[map[x][i].v]=color[x]; //非割边，即说明两个节点处在同以双连通分量中
Set_Color(map[x][i].v);
}
}
}


int DFSDP(int x,int dist)
{
done[x]=1;
dp[x]=dist;
int i,a;
for(i=0;i<newmap[x].size();i++)
{
if(!done[newmap[x][i].v])
{
a=DFSDP(newmap[x][i].v,newmap[x][i].w);
dp[x]=MinN(dp[x],a);
}
}
return dp[x];
}

void dfs(int x)
{
done[x]=1;
int min1=100001,min2=100001,i,v=-1;
for(i=0;i<newmap[x].size();i++)
{
if(!done[newmap[x][i].v])
{
if(dp[newmap[x][i].v]<=min1) {min2=min1;min1=dp[newmap[x][i].v];v=newmap[x][i].v;}
else if(dp[newmap[x][i].v]<=min2) min2=dp[newmap[x][i].v];
}
}
q=MinN(min2,q);
if(v!=-1) DFS(v);
}

int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
int a,b,w,i;
node tmp;
for(i=0;i<maxn;i++)
{
map[i].clear();
newmap[i].clear();
}
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&w);
tmp.v=b-1;tmp.w=w;
map[a-1].push_back(tmp);
tmp.v=a-1;
map[b-1].push_back(tmp);
}
index=1;
memset(DFn,0,sizeof(DFn));
DFS(0,-1);
memset(color,0,sizeof(color));
color[0]=1;
index=2;
minw=100001;
Set_Color(0);
memset(dp,-1,sizeof(dp));
memset(done,0,sizeof(done));
done[minu]=done[minv]=1;
DFSDP(minu,minw);
DFSDP(minv,minw);
q=100001;
memset(done,0,sizeof(done));
done[minu]=done[minv]=1;
dfs(minu);
dfs(minv);
if(q!=100001) printf("%d\n",q);
else printf("-1\n");
}
return 0;
}   回复  更多评论   

# re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解 2011-09-04 19:13 PWK

代码粘错啦，比赛的时候代码写的太挫啦，发现命名了2个DFS，后面那个改小写啦，粘的中每改。dfs函数中的dfs函数改成小写。
void dfs(int x)
{
done[x]=1;
int min1=100001,min2=100001,i,v=-1;
for(i=0;i<newmap[x].size();i++)
{
if(!done[newmap[x][i].v])
{
if(dp[newmap[x][i].v]<=min1) {min2=min1;min1=dp[newmap[x][i].v];v=newmap[x][i].v;}
else if(dp[newmap[x][i].v]<=min2) min2=dp[newmap[x][i].v];
}
}
q=MinN(min2,q);
if(v!=-1) dfs(v);
}  回复  更多评论   

# re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解[未登录] 2011-09-05 08:44 yzhw

@PWK
谢谢你~  回复  更多评论   

# re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解 2011-09-05 22:43 waterman

问问博主，对于1008，如果x在y为根的子树上，且最小值在x所在的这棵子树上，就取次小的值，那么如果次小的值也在x所在的这棵子树上，是否要继续考虑第三小的值呢？  回复  更多评论   

# re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解 2011-09-06 09:21 yzhw

@waterman
这里的次小值是节点P中儿子子树最小值的次小值，换句话说，假设把所有儿子子树的最小值放在一个列表中，然后排个序的话，该子树节点的次小值是排位第二的元素（当然实现的时候不用这样）。就是说，最小值和次小值不会处于同一颗子树上  回复  更多评论   

# re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解 2011-09-13 22:05 demo

ans2=min(ans2,1);这句直接ans2=1;就行了吧？  回复  更多评论