青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

# 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;就行了吧？  回復  更多評論