poj 3684 Destroy
题目大意:给定一棵树,每条边有两种权值(lenth:边的长度,power:去掉这条边需要的花费).有且仅有一个结点是中心:所有结点到该中心的距离中最大的最小.power=x的炸弹可以去掉所有power小于或等于x的边.问使得所有叶子结点与中心不相连的最小x值.题目思路:思路很明显,找出中心,再dfs求出中心到各个叶子结点的路的最小power值中的最大值.难点在于找中心.一次dfs,我们可以求出当前结点下的所有结点到当前结点的最远距离.(更新父节点的最远距离)有了第一次dfs的数据,再一次dfs,我们就可以求出所有结点到其他结点的最远距离了.(更新子节点的最远距离)但是再第一次dfs时我们还要保存两个值,who[]该最远距离来自哪个子结点,sec[]第二远距离.因为再第二次dfs时,如果更新子节点时,父节点的最远距离来自该子节点时,用父节点的最远距离去更新,显然是错误的,应该用第二远距离去更新.貌似这也算是一种树形DP来着...,那就算是我做的第一道树形DP吧..代码:[cpp]#include <stdlib.h>#include <string.h>#include <stdio.h>#include <ctype.h>#include <math.h>#include <stack>#include <queue>#include <map>#include <set>#include <vector>#include <string>#include <iostream>#include <algorithm>using namespace std;#define ll __int64#define ls rt<<1#define rs ls|1#define lson l,mid,ls#define rson mid+1,r,rs#define middle (l+r)>>1#define clr_all(x,c) memset(x,c,sizeof(x))#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))#define eps (1e-8)#define MOD 1000000007#define INF 0x3f3f3f3f#define PI (acos(-1.0))#pragma comment(linker, "/STACK:102400000,102400000")template <class T> T _max(T x,T y){return x>y? x:y;}template <class T> T _min(T x,T y){return x<y? x:y;}template <class T> T _abs(T x){return (x < 0)? -x:x;}template <class T> T _mod(T x,T y){return (x > 0)? x%y:((x%y)+y)%y;}template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}template <class T> void getmax(T& x,T y){x=(y > x)? y:x;}template <class T> void getmin(T& x,T y){x=(x<0 || y<x)? y:x;}int TS,cas=1;const int M=10000+5;int n;int fir[M],who[M],sec[M],ret;struct edge{int v,w,p;edge(){}edge(int _v,int _w,int _p){v=_v,w=_w,p=_p;}}edg[M<<1];vector<int>init[M];bool vis[M];void update(int u,int v,int len){if(fir[u] < len){sec[u] = fir[u];fir[u] = len;who[u] = v;}else getmax(sec[u],len);}void dfs1(int u){vis[u]=1;for(int i=0;i<init[u].size();i++){edge& e=edg[init[u][i]];if(vis[e.v]) continue;vis[e.v]=1;dfs1(e.v);update(u,e.v,fir[e.v]+e.w);}}void dfs2(int u){vis[u]=1;for(int i=0;i<init[u].size();i++){edge& e=edg[init[u][i]];if(vis[e.v]) continue;update(e.v,u,((who[u]!=e.v)? fir[u]:sec[u])+e.w);dfs2(e.v);}}void dfs(int u,int power){vis[u]=1;if(init[u].size() == 1){getmax(ret,power);return;}for(int i=0;i<init[u].size();i++){edge& e=edg[init[u][i]];if(vis[e.v]) continue;dfs(e.v,_min(e.p,power));}}void run(){int i,j;for(i=1;i<=n;i++)init[i].clear();for(i=1;i<n;i++){int u,v,w,p;scanf("%d%d%d%d",&u,&v,&w,&p);edg[(i-1)<<1]=edge(v,w,p);edg[(i-1)<<1|1]=edge(u,w,p);init[u].push_back((i-1)<<1);init[v].push_back((i-1)<<1|1);}clr(fir,0,n+1),clr(who,0,n+1),clr(sec,0,n+1);clr(vis,0,n+1),dfs1(1);clr(vis,0,n+1),dfs2(1);int ct=1;for(i=2;i<=n;i++){//printf("%d: %d %d %d\n",i,fir[i],who[i],sec[i]);if(fir[ct] > fir[i]) ct=i;}//printf("center = %d\n",ct);clr(vis,0,n+1),ret=-INF,dfs(ct,INF);printf("%d\n",ret);}void preSof(){}int main(){//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);preSof();//run();while((~scanf("%d",&n))) run();//for(scanf("%d",&TS);cas<=TS;cas++) run();return 0;}
补充：Web开发 , ASP.Net ,
