亚洲国产精品成人综合,免费人成精品欧美精品,久久天天综合

re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC�|�络�?个�h题解

demo — Tue, 13 Sep 2011 14:05:00 GMT

ans2=min(ans2,1);�q�句直接ans2=1;��p��了吧�Q?img src ="http://www.shnenglu.com/yzhw/aggbug/155702.html" width = "1" height = "1" />

demo 2011-09-13 22:05 发表评论

re: The 36th ACM/ICPC Asia Regional Shanghai Site —�?Warmup 个�h题解

yzhw — Thu, 08 Sep 2011 04:10:00 GMT

@tjt
有一题当时算法对的，用C++没过。后来用java�q�掉�?br>呵呵~我不是说比赛时候做�?�?img src ="http://www.shnenglu.com/yzhw/aggbug/155343.html" width = "1" height = "1" />

yzhw 2011-09-08 12:10 发表评论

re: The 36th ACM/ICPC Asia Regional Shanghai Site —�?Warmup 个�h题解

tjt — Thu, 08 Sep 2011 01:35:00 GMT

怎么�H�然又成�?题了呢~~

tjt 2011-09-08 09:35 发表评论

re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC�|�络�?个�h题解

yzhw — Tue, 06 Sep 2011 01:21:00 GMT

@waterman
�q�里的次��值是节点P中儿子子树最��值的�ơ小��|��换句话说�Q�假设把所有儿子子树的最��值放在一个列表中�Q�然后排个序的话�Q�该子树节点的次��值是排位�W�二的元素（当然实现的时候不用这��P��。就是说�Q�最��值和�ơ小��g��会处于同一颗子树上

yzhw 2011-09-06 09:21 发表评论

re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC�|�络�?个�h题解

waterman — Mon, 05 Sep 2011 14:43:00 GMT

问问博主�Q�对�?008�Q�如果x在y为根的子树上�Q�且最��值在x所在的�q�棵子树上，��取�ơ小的��|��那么如果�ơ小的��g��在x所在的�q�棵子树上，是否要��l�考虑�W�三��的值呢�Q?img src ="http://www.shnenglu.com/yzhw/aggbug/155164.html" width = "1" height = "1" />

waterman 2011-09-05 22:43 发表评论

re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC�|�络�?个�h题解[未登录]

yzhw — Mon, 05 Sep 2011 00:44:00 GMT

@PWK
谢谢你~

yzhw 2011-09-05 08:44 发表评论

re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC�|�络�?个�h题解

PWK — Sun, 04 Sep 2011 11:13:00 GMT

代码�_�错啦，比赛的时候代码写的太挫啦�Q�发现命名了2个DFS�Q�后面那个改��写啦，�_�的中每攏V��dfs函数中的dfs函数�Ҏ(gu��)��写�?br>void dfs(int x)
{
done[x]=1;
int min1=100001,min2=100001,i,v=-1;
for(i=0;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);
}

PWK 2011-09-04 19:13 发表评论

re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC�|�络�?个�h题解

PWK — Sun, 04 Sep 2011 11:08:00 GMT

补上1005题目思�\�Q�在�q�题的思�\是对点进行割边的�~�点从构图，如果2�?�q�通，那么他们�q�通的�Ҏ(gu��)��不能破坏的。能破坏的只有割辏V��由void DFS(int x,int farther) �Q�void Set_Color(int x)完成。完成后成�ؓ一��|��。之后就是博弈问题啦�Q�做完敌人，他们要找��C��条链�Q��得能��量多的删除最��的辏V��不能删除的最��边权值则是这题的解。删除最��的边的�Ҏ(gu��)��是以最��边的两个点为根�Q�分别构建树�Q�树形DP�Q�求节点下面的哪条�\有最��边�Q�找��C��走的边的最��权倹{��输出�?br>#include
#include
using namespace std;
#define maxn 10005
int MinN(int x,int y) {return xstruct node{int v,w;};
vector map[maxn],newmap[maxn];
int DFn[maxn]; //深搜时节点的讉K��序
int low[maxn]; //存放当前接点不经�q�其父亲节点能够讉K��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 {
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]);//��查从自��n出发的后向边�Q�无向图中没有横叉边�Q?
}
}
void Set_Color(int x)//染色�Q�同一双连通分量内的节点用一�U�颜�?
{
int i;
node tmp;
for(i=0;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=map[x][i].w;
minu=color[x];
minv=color[map[x][i].v];
}
}
else color[map[x][i].v]=color[x]; //非割边，卌��明两个节点处在同以双�q�通分量中
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 {
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 {
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 {
map[i].clear();
newmap[i].clear();
}
for(i=0;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;
}

PWK 2011-09-04 19:08 发表评论

re: pku 1180 Batch Scheduling �l�典斜率优化

ningbohezhijun — Mon, 04 Apr 2011 06:27:00 GMT

博主�Q�此题感觉很难，自认为勉强看懂吧�Q�但是�ؓ什么说�q�题很经典呢�Q�有什么推�q��h(hu��n)值吗�Q?img src ="http://www.shnenglu.com/yzhw/aggbug/143399.html" width = "1" height = "1" />

ningbohezhijun 2011-04-04 14:27 发表评论