C++博客-yzhw@ujs code my life~-最新评论http://www.cppblog.com/yzhw/CommentsRSS.aspx江苏大学zh-cnFri, 09 Nov 2012 03:04:00 GMTFri, 09 Nov 2012 03:04:00 GMTcnblogsre: pku 3998 Land Division DP斜率优化http://www.cppblog.com/yzhw/archive/2012/05/23/158598.html#175839lzqxhlzqxhTue, 22 May 2012 17:55:00 GMThttp://www.cppblog.com/yzhw/archive/2012/05/23/158598.html#175839把每个点的权值设为m，则每部分平均权值为n。之后转为整数操作
之后，我离散化点Tle了。证明大数据比较多，离散化优势在于处理小数据，但是大数据复杂度退化成O(nlogn)。。
之后改成原坐标直接作为dp状态。。400+msAc了
最后：好像是贪心+单调队列。。没有发现用到斜率的地方啊

lzqxh 2012-05-23 01:55 发表评论
]]>re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解http://www.cppblog.com/yzhw/archive/2011/09/13/155042.html#155702demodemoTue, 13 Sep 2011 14:05:00 GMThttp://www.cppblog.com/yzhw/archive/2011/09/13/155042.html#155702

demo 2011-09-13 22:05 发表评论
]]>re: The 36th ACM/ICPC Asia Regional Shanghai Site —— Warmup 个人题解http://www.cppblog.com/yzhw/archive/2011/09/08/155307.html#155343yzhwyzhwThu, 08 Sep 2011 04:10:00 GMThttp://www.cppblog.com/yzhw/archive/2011/09/08/155307.html#155343有一题当时算法对的，用C++没过。后来用java过掉了
呵呵~我不是说比赛时候做出6题

yzhw 2011-09-08 12:10 发表评论
]]>re: The 36th ACM/ICPC Asia Regional Shanghai Site —— Warmup 个人题解http://www.cppblog.com/yzhw/archive/2011/09/08/155307.html#155327tjttjtThu, 08 Sep 2011 01:35:00 GMThttp://www.cppblog.com/yzhw/archive/2011/09/08/155307.html#155327

tjt 2011-09-08 09:35 发表评论
]]>re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解http://www.cppblog.com/yzhw/archive/2011/09/06/155042.html#155190yzhwyzhwTue, 06 Sep 2011 01:21:00 GMThttp://www.cppblog.com/yzhw/archive/2011/09/06/155042.html#155190这里的次小值是节点P中儿子子树最小值的次小值，换句话说，假设把所有儿子子树的最小值放在一个列表中，然后排个序的话，该子树节点的次小值是排位第二的元素（当然实现的时候不用这样）。就是说，最小值和次小值不会处于同一颗子树上

yzhw 2011-09-06 09:21 发表评论
]]>re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解http://www.cppblog.com/yzhw/archive/2011/09/05/155042.html#155164watermanwatermanMon, 05 Sep 2011 14:43:00 GMThttp://www.cppblog.com/yzhw/archive/2011/09/05/155042.html#155164

waterman 2011-09-05 22:43 发表评论
]]>re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解[未登录]http://www.cppblog.com/yzhw/archive/2011/09/05/155042.html#155107yzhwyzhwMon, 05 Sep 2011 00:44:00 GMThttp://www.cppblog.com/yzhw/archive/2011/09/05/155042.html#155107谢谢你~

yzhw 2011-09-05 08:44 发表评论
]]>re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解http://www.cppblog.com/yzhw/archive/2011/09/04/155042.html#155063PWKPWKSun, 04 Sep 2011 11:13:00 GMThttp://www.cppblog.com/yzhw/archive/2011/09/04/155042.html#155063void 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);
}

PWK 2011-09-04 19:13 发表评论
]]>re: The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛 个人题解http://www.cppblog.com/yzhw/archive/2011/09/04/155042.html#155062PWKPWKSun, 04 Sep 2011 11:08:00 GMThttp://www.cppblog.com/yzhw/archive/2011/09/04/155042.html#155062#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;
}

PWK 2011-09-04 19:08 发表评论
]]>re: pku 1180 Batch Scheduling 经典斜率优化http://www.cppblog.com/yzhw/archive/2011/04/04/137929.html#143399ningbohezhijunningbohezhijunMon, 04 Apr 2011 06:27:00 GMThttp://www.cppblog.com/yzhw/archive/2011/04/04/137929.html#143399

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