注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

NOI2013 题解  

2013-07-15 18:49:25|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
挖个坑
day1 T1
非常神的方法
由于没能去现场听到题解,所以是进队爷孙周易大神转述的
先考虑k=2,做法如下:
我们先把题目输入的一堆向量给变成一个矩阵A
然后弄出他的转置,也就是旋转90度,得到矩阵B
假设C=A*B
A,B,C,D非零即1
现在我们就是要寻找C的一个除了主对角线上的非0元素,那个元素的位置(i,j)就是答案了
但是直接做是不好做的,我们这样来看:
C的主对角线是可以暴力计算的,这一步的时间复杂度只有O(nd),可以接受
我们构造一个矩阵D,D的主对角线就是C的主对角线,D的其他元素都是1
显然C,D都是直接爆空间的矩阵,所以都是不可能真的算出来的拉。不过我们可以用一个数组记录C的主对角线,这样至少D就可以表示出来了。
现在我们判断,A*B==D的正确性
请看bzoj 2396
一个非常神奇的算法,构造一个1*n的矩阵(其实就是向量)x,判断x*A*B==x*D,这就可以过那道题目了,因为那是N^2的
这道题目的话,也一样用着个方法,判断x*A*B是否等于x*D
由于A,B的是n*d和d*n的,这是可以接受的。但是D是n*n的
可是D具有很大的特殊性质,可以随便搞搞搞出来吧?就是先算出sigma(x[i]*D[1][i]),然后sigma(x[i]*D[2][i])就是第一个的答案-x[1]*D[1][1]+x[1]+x[2]*D[1][2]-x[2],反正差不多这样就可以算出来了
但是题目不是要你判断是否存在而是要你找到一对可行的啊,所以还要继续看。
如果第i个位置不同,那么一定有有i的可行答案,我们再去暴力枚举j,就可以在O(nd)的时间解决k=2的了
现在考虑k=3
k=3的问题在于D矩阵除主对角线外的元素,不能全看成1了,还有2要考虑
但是1*1 mod 3 = 1,2*2 mod 3 = 1
我们把一个n行d列的矩阵扩展成n行d*d列
对于第i行,本来是x[i][1],x[i][2],x[i][3]……x[i][d],我们变成x[i][j]*x[i][k] 1<=j,k<=d
这样一来,重复上面的步骤,那么D除了主对角线外的数就只可能是1了,因为1,2的平方mod 3都等于1
然后再用上面的算法,时间复杂度O(n*d*d)
吐槽:数据范围的过于巨大,让我不得不把矩阵压成了一维数组;并且由于我的方法要开a,b两个矩阵,最后我只好用short解决空间问题。没办法,时间可以用调大时限来放宽,空间在OI比赛中512MB不能更多了
一点奇葩东西
为了卡常数,我没有随机向量,而是使用(1,1,1……)这个无聊向量
这样只要一次就行了(实在不知道出题人随机14次是怎么玩的)
似乎正确率还行(暂时还没测,测了后三组)
然后仍然是快乐的卡常数日子
傻逼的YDC卡啊卡啊卡
最后发现傻逼的YDC把A的转置算出来并存下来了
于是没有计算A的转置,卡掉了一个常数
最后发现傻逼的YDC多次进行a*b(a,b<=3)的计算
于是开了个数组存下来
最后傻逼的YDC发现一个(i-1)*d+j的函数调用了几亿次
于是每个地方都手写

并不建议看代码
很多地方为了卡常数,所以可读性不强
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#define maxn 100000002
using namespace std;
void Read(int &digit)
{
digit=0;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
int n,d,mod;
short mul[4][4];
short A[maxn];
short matrix[100010][110];
short v[100010];
void read()//Get Matrix A
{
int top=0;
Read(n),Read(d),Read(mod);
for(int i=0;i<=mod-1;i++)
for(int j=0;j<=mod-1;j++)
mul[i][j]=i*j%mod;
for(int i=1,p;i<=n;i++)
for(int j=1;j<=d;j++)
{
Read(p);
matrix[i][j]=p%mod;
A[++top]=matrix[i][j];
}
if(mod==3)
{
top=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++)
for(int k=1;k<=d;k++)
A[++top]=mul[matrix[i][j]][matrix[i][k]];
d=d*d;
}
}
void Prepare()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++)
{
v[i]=v[i]+mul[A[(i-1)*d+j]][A[(i-1)*d+j]];
if(v[i]>=mod)
v[i]-=mod;
}
}
pair<int,int> Find(short a[],short b[])
{
int x=0;
for(int i=1;i<=n;i++)
if(a[i]!=b[i])
{
x=i;
break;
}
if(x==0)
return make_pair(-1,-1);
if(mod==3)
d=(int)sqrt(d);
for(int i=1;i<=n;i++)
if(i!=x)
{
int s=0;
for(int j=1;j<=d;j++)
{
s=s+mul[matrix[i][j]][matrix[x][j]];
if(s>=mod)
s-=mod;
}
if(s==0)
{
if(x>i)
swap(x,i);
return make_pair(x,i);
}
}
return make_pair(-1,-1);
}
void work()
{
static short sum1[100010],sum2[100010];
for(int i=1;i<=d;i++)
{
int sum=0;
for(int j=1;j<=n;j++)
sum=sum+A[(j-1)*d+i];
sum1[i]=sum%mod;
}
for(int i=1;i<=n;i++)
{
int sum=0;
for(int j=1;j<=d;j++)
sum=sum+mul[sum1[j]][A[(i-1)*d+j]];
sum2[i]=sum%mod;
}
for(int i=1;i<=n;i++)
sum1[i]=(n-1+v[i])%mod;
pair<int,int> ans=Find(sum1,sum2);
printf("%d %d\n",ans.first,ans.second);
}
int main()
{
freopen("meow.in","r",stdin);
freopen("meow.out","w",stdout);
read();
Prepare();
work();
fclose(stdin);
fclose(stdout);
return 0;
}

day2 T2
首先膜拜不得了大神考场上怒A此题
考虑两个BFS序相邻点,要么他们没关系,要么他们只能是父子,要么既能是父子还能是兄弟
如果对于BFS序内相邻点A,B,A在DFS序的位置大于B在DFS序的位置,有且只有一种可能,就是到了新的一层,这时高度自然++
但是还有一种可能,就是既能是父子还能是兄弟。这种情况的判定条件我们暂且不提,考虑如果求出了有多少这样的点,答案如何变?
假设第一种可能的高度累加量是d1,第二种的累加量是d2,总树的个数就是2^d2,平均深度是(d1*(2^d2)+x)/(2^d2),x是枚举他有多少个第二种可能的点为父子关系(因为父子关系要高度增加)
那个式子等于d1+Σx/(2^d2),Σx=ΣC(d2,i)*i=2^(d2-1)*d2,所以式子等于d1+d2*0.5
d1用上面讲的判定条件即可
d2的话,对于BFS序内相邻点a,b,首先他们在DFS序内的位置必须相邻吧
然后如果存在一个点,其BFS序在a,b之前,DFS序又在a,b之后,a,b不能是父子,这一点可以画图(如果不理解,可以按自己的想法写,拿错误的小数据调试就会知道了)
而类似的,还有一个条件是,不存在点,DFS序在a,b之前,BFS序在a,b之后。
要快速判断,很容易用各种前缀最小值搞出来
但是还有一个特殊情况
就是如果BFS序里最后若干个数他们在DFS序是相连续的,那么没算过的点也要计算
这点可以用第三个测试点调试理解
其实我自己也很不放心,真的不明白为什么不会有别的特殊情况

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 200010
using namespace std;
double ans;
int n,BFS[maxn],DFS[maxn],posB[maxn],posD[maxn];
void read()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&DFS[i]);
posD[DFS[i]]=i;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&BFS[i]);
posB[BFS[i]]=i;
}
}
void solve()
{
static int max1[maxn],max2[maxn];
static bool use[maxn];
for(int i=1;i<=n;i++)
{
max1[i]=max(max1[i-1],posB[DFS[i]]);
max2[i]=max(max2[i-1],posD[BFS[i]]);
}
ans=2;
for(int i=3;i<=n;i++)
{
if(posD[BFS[i-1]]>posD[BFS[i]])
ans++;
else if(posD[BFS[i-1]]==posD[BFS[i]]-1&&max1[posD[BFS[i]]]==i&&max2[posB[DFS[i]]]==posD[BFS[i]])
use[i]=true;
}
for(int i=n;i>=3&&posD[BFS[i-1]]==posD[BFS[i]]-1;i--)
use[i]=true;
for(int i=1;i<=n;i++)
if(use[i])
ans+=0.5;
printf("%.3lf\n%.3lf\n%.3lf\n",ans-0.001,ans,ans+0.001);
}
int main()
{
read();
solve();
return 0;
}



day2 T1
我们知道F[i]=a*F[i-1]+b除了用矩乘,还可以计算通项公式吧?
那么就可以很快由F[1][1]推到F[1][m]了
然后F[1][1]推到F[i][1]也就很容易用通项公式搞了
那么就很好搞了
现在还有个问题是要算a^n%mod,n是高精度数,这个怎么算呢?
其实就是a^(n%(phi(mod)))%mod,也就是a^(n%(mod-1))%mod
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
#define maxn 1010
#define maxs 1000010
using namespace std;
typedef long long LL;
const int mod=1000000007;
const int phi=mod-1;
struct bign
{
int n,digit[maxs];
void Read()
{
char c;
for(c=getchar();!isdigit(c);c=getchar());
for(;isdigit(c);digit[++n]=c-'0',c=getchar());
}
friend int operator % (const bign &a,LL p)
{
LL rem=0;
for(int i=1;i<=a.n;i++)
{
rem=rem*10+a.digit[i];
while(rem>=p)
rem-=p;
}
return rem;
}
}N,M;
LL a,b,c,d;
LL power(LL p,LL n)
{
LL ans=1;
for(;n;n>>=1,p=p*p%mod)
if(n&1)
ans=ans*p%mod;
return ans;
}
LL anti(LL p)
{
return power(p,mod-2);
}
LL F1(LL x,LL b,int n)//F[1]=x,F[i]=F[i-1]+b,calc F[n]
{
return (x+b*n)%mod;
}
LL F2(LL x,LL a,LL b,int n)//F[1]=x,F[i]=F[i-1]*a+b,calc F[n]
{
LL b1=(x*(a-1)+b)%mod,bn=b1*power(a,n-1)%mod;
return (bn-b+mod)%mod*anti(a-1)%mod;
}
LL calc1()
{
int n=N%phi,m=(M%mod-1+mod)%mod;
LL B=(b*m%mod*c+d)%mod;
LL p1=c==1?F1(1,B,(N%mod-1+mod)%mod):F2(1,c,B,n);
return (p1+b*m)%mod;
}
LL calc2()
{
int n=N%phi,m=(M%phi-1+phi)%phi;
LL lamda=b*anti(a-1)%mod,t=power(a,m);
LL p1=F2(1,t*c%mod,(t*lamda%mod*c%mod-lamda*c%mod+d+2*mod)%mod,n);
return F2(p1,a,b,m+1);
}
void work()
{
if(a==1)
cout<<calc1()<<endl;
if(a!=1)
cout<<calc2()<<endl;
}
int main()
{
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
N.Read(),M.Read();
cin>>a>>b>>c>>d;
work();
fclose(stdin);
fclose(stdout);
return 0;
}


day2 T2
没想到最后常数还是没卡过去
靠着bzoj的总用时限制过掉了
时间倒数第一
方法肯定是N,O,I独立考虑
我的N,I都是n^2m的,O是nm^2的
但是O的用时反倒是微乎其微……
反倒是n^2m的N让我超时
不过也正常,我的写法常数大到爆了
方法是DP已经很显然了
对于N,分成三部分,左边一竖,中间斜的,右边一竖。F[i][j][k][t]表示矩形上面是i,下面是j,右边在第k列,第t个部分(0<=t<=2)的最大值
对于左边一竖,直接由F[i][j][k-1][0]转移到F[i][j][k][0]
对于右边一竖,直接由F[i][j][k-1][2]与F[i][j'][k-1][1]转移到F[i][j][k][2],i<=j'<j。所以我们在计算出F[i][j][k][1]后,可以用个辅助数组max2,max2[i][j]表示j'在i~j里,F[i][j'][k-1][1]的最值对于中间,F[i][j][k][1]首先可以由F[i'][j][k-1][0],i'<i,这一步跟上面很像
然后F[i][j][k][1]可以由F[i'][j'][k-1][1]转移,i<=i'<=j+1 j<=j'。这一步很难一个数组维护极值,我们考虑利用max2。这样一来,再开max3[i][j]表示i<=i'<=j+1,j<=j'<=nRow里,F[i'][j'][k-1][1]的最值就可以利用max2来推了
于是N终于搞出来了
O I 就比较容易了
I的话,拆成三部分,右边、中间一竖、左边,然后F[i][j][k][2]由F[i][j][k+1][2]递推,F[i][j][k][1]由F[i][j][k+1][2]与F[i][j][k+1][1]递推,F[i][j][k][0]由F[i][j][k+1][0]与F[i][j][k+1][1]递推
O的话,我用了个nm^2的做法,枚举左右边界,从下往上扫上边界,扫描的时候顺便维护下边解的最优决策点
再开两个数组Fn[i],Fi[i]分别表示1~i的最大的N以及i~nCol的最大的I
计算O的时候,枚举左右边界,拿两边的NI与这一块里最大的O更新答案
同样不建议看代码,因为为了卡常数可读性不强(虽然没卡过去)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#define maxn 151
#define maxm 501
#define INF 500000000
using namespace std;
int nRow,nCol,map[maxn][maxm];
int N[maxn][maxn][maxm][3],I[maxn][maxn][maxm][3];
int Fn[maxm],Fi[maxm];
int sum[maxn][maxm];
void read()
{
scanf("%d %d",&nRow,&nCol);
for(int i=nRow;i>=1;i--)
for(int j=1;j<=nCol;j++)
{
scanf("%d",&map[i][j]);
sum[i][j]=map[i][j];
}
for(int i=1;i<=nRow;i++)
for(int j=1;j<=nCol;j++)
sum[i][j]=sum[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
for(int i=1;i<=nRow;i++)
for(int j=i;j<=nRow;j++)
for(int k=1;k<=nCol;k++)
for(int r=0;r<=2;r++)
N[i][j][k][r]=I[i][j][k][r]=-INF;
for(int i=1;i<=nCol;i++)
Fn[i]=-INF,Fi[i]=-INF;
}
void Dp()
{
static int max1[maxn][maxn][maxm],max2[maxn][maxn],max3[maxn][maxn];
//calc "N" Left
for(int j=1;j<=nRow;j++)
for(int k=1;k<=nCol;k++)
{
max1[0][j][k]=-INF;
for(int i=1;i<=j;i++)
{
int area=sum[j][k]-sum[i-1][k]-sum[j][k-1]+sum[i-1][k-1];
N[i][j][k][0]=area+N[i][j][k-1][0];
if(N[i][j][k][0]<area)
N[i][j][k][0]=area;
max1[i][j][k]=max1[i-1][j][k];
if(max1[i][j][k]<N[i][j][k][0])
max1[i][j][k]=N[i][j][k][0];
}
}
//calc "N" Middle & "N" Right
for(int k=2;k<nCol;k++)
{
for(int i=1;i<=nRow;i++)
for(int j=i;j<=nRow;j++)
{
int v=sum[j][k]-sum[i-1][k]-sum[j][k-1]+sum[i-1][k-1];
//N[i][j][k][1]=max{N[i'][j][k-1][0]}+Sum(i,k,j,k) i'<i
if(N[i][j][k][1]<max1[i-1][j][k-1]+v)
N[i][j][k][1]=max1[i-1][j][k-1]+v;
//N[i][j][k][1]=max{N[i'][j'][k-1][1]}+Sum(i,k,j,k)
//i'>=i i'-1<=j<=j'
//i<=i'<=j+1 j<=j'
//i'<=j'
//i' [i,j+1] j' [j,nRow] i'<=j'
if(k>2&&j<nCol&&N[i][j][k][1]<max3[i][j]+v)
N[i][j][k][1]=max3[i][j]+v;
}
max2[nRow][nRow]=N[nRow][nRow][k][1];
for(int i=1;i<=nRow;i++)
{
max2[i][nRow]=N[i][nRow][k][1];
for(int j=nRow-1;j>=i;j--)
{
max2[i][j]=N[i][j][k][1];
if(max2[i][j]<max2[i][j+1])
max2[i][j]=max2[i][j+1];
}
}
max3[nRow][nRow]=N[nRow][nRow][k][1];
for(int i=nRow-1;i>=1;i--)
{
max3[i][nRow]=max2[i][nRow];
if(max3[i][nRow]<max3[i+1][nRow])
max3[i][nRow]=max3[i+1][nRow];
}
for(int j=nRow-1;j>=1;j--)
{
max3[j][j]=max2[j][j];
if(max3[j][j]<max2[j+1][j+1])
max3[j][j]=max2[j+1][j+1];
for(int i=j-1;i>=1;i--)
{
max3[i][j]=max2[i][j];
if(max3[i][j]<max3[i+1][j])
max3[i][j]=max3[i+1][j];
}
}
for(int i=1;i<=nRow;i++)
{
max2[i][i]=N[i][i][k][1];
for(int j=i+1;j<=nRow;j++)
{
max2[i][j]=max2[i][j-1];
if(max2[i][j]<N[i][j][k][1])
max2[i][j]=N[i][j][k][1];
}
}
for(int i=1;i<=nRow;i++)
for(int j=i+1;j<=nRow;j++)
{
//N[i][j][k][2]=max{N[i][j'][k-1][1]}+Sum(i,k,j,k) j'<j
int v=sum[j][k+1]-sum[i-1][k+1]-sum[j][k]+sum[i-1][k];
if(N[i][j][k+1][2]<max2[i][j-1]+v)
N[i][j][k+1][2]=max2[i][j-1]+v;
if(N[i][j][k+1][2]<N[i][j][k][2]+v)
N[i][j][k+1][2]=N[i][j][k][2]+v;
if(Fn[k+1]<N[i][j][k+1][2])
Fn[k+1]=N[i][j][k+1][2];
}
}
for(int i=4;i<=nCol;i++)
if(Fn[i]<Fn[i-1])
Fn[i]=Fn[i-1];
//calc "I" Right
for(int i=1;i<=nRow;i++)
for(int j=i+2;j<=nRow;j++)
{
I[i][j][nCol][2]=map[i][nCol]+map[j][nCol];
for(int k=nCol-1;k>=1;k--)
{
I[i][j][k][2]=I[i][j][k+1][2]+map[i][k]+map[j][k];
if(I[i][j][k][2]<map[i][k]+map[j][k])
I[i][j][k][2]=map[i][k]+map[j][k];
}
}
//calc "I" Middle
for(int i=1;i<=nRow;i++)
for(int j=i+2;j<=nRow;j++)
{
I[i][j][nCol-1][1]=sum[j][nCol-1]-sum[i-1][nCol-1]-sum[j][nCol-2]+sum[i-1][nCol-2]+I[i][j][nCol][2];
for(int k=nCol-2;k>=1;k--)
{
int area=sum[j][k]-sum[i-1][k]-sum[j][k-1]+sum[i-1][k-1];
I[i][j][k][1]=I[i][j][k+1][2]+area;
if(I[i][j][k][1]<I[i][j][k+1][1]+area)
I[i][j][k][1]=I[i][j][k+1][1]+area;
}
}
//calc "I" Left
for(int i=1;i<=nRow;i++)
for(int j=i+2;j<=nRow;j++)
{
I[i][j][nCol-2][0]=map[i][nCol-2]+map[j][nCol-2]+I[i][j][nCol-1][1];
if(Fi[nCol-2]<I[i][j][nCol-2][0])
Fi[nCol-2]=I[i][j][nCol-2][0];
for(int k=nCol-3;k>=1;k--)
{
I[i][j][k][0]=I[i][j][k+1][1];
if(I[i][j][k][0]<I[i][j][k+1][0])
I[i][j][k][0]=I[i][j][k+1][0];
I[i][j][k][0]=I[i][j][k][0]+map[i][k]+map[j][k];
if(Fi[k]<I[i][j][k][0])
Fi[k]=I[i][j][k][0];
}
}
for(int i=nCol-3;i>=1;i--)
if(Fi[i]<Fi[i+1])
Fi[i]=Fi[i+1];
//calc ans
int ans=-INF;
for(int i=5;i<=nCol-4;i++)
for(int j=i+2;j<=nCol-4;j++)
{
int va=Fn[i-2],vb=Fi[j+2],maxv=sum[1][j-1]-sum[1][i],Fo;
Fo=sum[3][j]-sum[3][i-1]-sum[2][j-1]+sum[1][j-1]+sum[2][i]-sum[1][i];
int t=sum[2][j-1]-sum[1][j-1]-sum[2][i]+sum[1][i]-map[1][i]-map[1][j];
if(maxv<t)
maxv=t;
for(int k=4;k<=nRow;k++)
{
int t1=sum[k][j]-sum[k][i-1]+sum[k-1][i]-sum[k-1][j-1]+maxv;
int t2=sum[k-1][j-1]-sum[k-1][i]+sum[k-2][i-1]-sum[k-2][j];
if(Fo<t1)
Fo=t1;
if(maxv<t2)
maxv=t2;
}
if(ans<va+vb+Fo)
ans=va+vb+Fo;
}
printf("%d\n",ans);
}
int main()
{
freopen("penman.in","r",stdin);
freopen("penman.out","w",stdout);
read();
Dp();
fclose(stdin);
fclose(stdout);
return 0;
}

day2 T3
这题还是挺好的
首先这是树上弄一条边,弄出一个环
找环
先想60分做法,枚举删环上的边,然后求剩下的树的直径/2,取最小值即可
事实上很可惜的是我考场上没想出来,想了个超级无敌逗逼的60分做法,直接导致代码量倍增然后每调出来最后这题爆零(T_T)
那么我们试着考虑证明?
然后发现是多么多么显然的结论啊
答案>=这个值;我又能构造出方案使得快餐店离最远点的距离是这个,所以这个就是答案了
接下来考虑如何做100分
把环去掉后剩下一些互相独立的联通块。先拿联通块内的直径更新答案,否则只有75分
对于环上的第i个点,预处理d[i]表示他到他所在的联通块的最远点距离。
假设把环的某一条边删掉(比如把环上的第n个点和第1个点的边删掉),现在就是一条链,我们可以记录S[i]表示i的前缀和,即环上1号点到环上i号点的距离
这样就可以用max{S[i]-S[j]+d[i]+d[j] i!=j}更新答案
我们维护max{S[i]+d[i]},max{d[i]-S[i]},当然由于i!=j,我们还要再维护次大值,还有维护最大值是由哪个点转移来的
这样询问就很容易了
考虑修改
就是把一条删掉的边加上,在删去下一条边,这就是一堆点的S值减少同一个值,然后某个点单点修改
用你喜欢的数据结构维护他吧!
我用了个线段树
时间复杂度O(n log n)

听@z55250825说这题是bzoj 1023的弱化版
赶快回去看了,一口鲜血喷出来
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 100010
#define maxm 200010
#define it tree[root]
#define lson tree[root<<1]
#define rson tree[root<<1|1]
#define INF 1000000000000000LL
using namespace std;
typedef long long LL;
LL d[maxn],Sum[maxn],ans,disCir;
int Cir[maxn],nCir;
int nPoint,dfn[maxn],id,father[maxn],edge[maxn];
int nEdge=1,to[maxm],next[maxm],len[maxm],start[maxn];
bool isCir[maxm];
struct Node
{
int p;
LL dis;
Node() {}
Node(int p,LL dis): p(p),dis(dis) {}
};
struct msgnode
{
LL max1,max2,max3,max4;
int num1,num2;
friend msgnode operator + (const msgnode &a,const msgnode &b)
{
msgnode c;
c.max1=a.max1,c.max2=b.max1,c.max3=a.max3,c.max4=b.max3;
c.num1=a.num1,c.num2=a.num2;
if(c.max1<c.max2)
{
swap(c.max1,c.max2);
c.num1=b.num1;
}
if(c.max3<c.max4)
{
swap(c.max3,c.max4);
c.num2=b.num2;
}
c.max2=max(c.max2,max(a.max2,b.max2));
c.max4=max(c.max4,max(a.max4,b.max4));
return c;
}
};
struct tagnode
{
LL add;
tagnode()
{
add=0;
}
};
struct Seg_Tree
{
msgnode msg;
tagnode tag;
}tree[maxn<<2];
void Read(int &digit)
{
digit=0;
static char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
void make(int a,int b,int c)
{
nEdge++,to[nEdge]=b,next[nEdge]=start[a],start[a]=nEdge,len[nEdge]=c;
}
void read()
{
Read(nPoint);
for(int i=1,a,b,c;i<=nPoint;i++)
{
Read(a),Read(b),Read(c);
make(a,b,c),make(b,a,c);
}
}
void FindCircle(int p)
{
dfn[p]=++id;
for(int i=start[p];i;i=next[i])
if(to[i]!=father[p])
{
int q=to[i];
if(dfn[q]==0)
{
father[q]=p,edge[q]=i;
FindCircle(q);
}
else if(dfn[q]<dfn[p])
{
isCir[i]=isCir[i^1]=true;
disCir+=len[i];
for(int i=p;i!=q;i=father[i])
{
isCir[edge[i]]=isCir[edge[i]^1]=true;
Cir[++nCir]=i;
disCir+=len[edge[i]];
}
Cir[++nCir]=q;
}
}
}
pair<LL,int> BFS(int Point)
{
static Node queue[maxn];
static bool use[maxn];
int front=0,rear=1;
LL ans=0;
int id=Point;
queue[rear]=Node(Point,0),use[Point]=true;
while(front<rear)
{
Node p=queue[++front];
for(int i=start[p.p];i;i=next[i])
if(!isCir[i]&&use[to[i]]==false)
{
use[to[i]]=true;
queue[++rear]=Node(to[i],p.dis+len[i]);
if(ans<queue[rear].dis)
ans=queue[rear].dis,id=queue[rear].p;
}
}
for(int i=1;i<=rear;i++)
use[queue[i].p]=false;
return make_pair(ans,id);
}
void Prepare()
{
for(int i=1;i<=nCir;i++)
{
pair<LL,int> temp=BFS(Cir[i]);
d[i]=temp.first;
ans=max(ans,BFS(temp.second).first);
BFS(Cir[i]);
}
}
void Build(int root,int l,int r)
{
if(l==r)
{
it.msg.max1=Sum[l]+d[l];
it.msg.max2=-INF;
it.msg.num1=l;
it.msg.max3=d[l]-Sum[l];
it.msg.max4=-INF;
it.msg.num2=l;
return ;
}
int mid=(l+r)>>1;
Build(root<<1,l,mid);
Build(root<<1|1,mid+1,r);
it.msg=lson.msg+rson.msg;
}
void update_add(int root,LL v)
{
it.msg.max1+=v;
it.msg.max2+=v;
it.msg.max3-=v;
it.msg.max4-=v;
it.tag.add+=v;
}
void push_down(int root)
{
if(it.tag.add)
{
update_add(root<<1,it.tag.add);
update_add(root<<1|1,it.tag.add);
it.tag.add=0;
}
}
void Set(int root,int l,int r,int p,LL v)
{
if(l==r)
{
it.msg.max1=v+d[l];
it.msg.max2=-INF;
it.msg.num1=l;
it.msg.max3=d[l]-v;
it.msg.max4=-INF;
it.msg.num2=l;
return ;
}
int mid=(l+r)>>1;
push_down(root);
if(p<=mid)
Set(root<<1,l,mid,p,v);
else
Set(root<<1|1,mid+1,r,p,v);
it.msg=lson.msg+rson.msg;
}
LL Query(int root)
{
if(it.msg.num1==it.msg.num2)
return max(it.msg.max1+it.msg.max4,it.msg.max2+it.msg.max3);
return it.msg.max1+it.msg.max3;
}
void Delete_Edge()
{
for(int i=2;i<=nCir;i++)
Sum[i]=Sum[i-1]+len[edge[Cir[i-1]]];
Build(1,1,nCir);
LL mind;
mind=Query(1);
for(int i=2;i<=nCir;i++)
{
update_add(1,-len[edge[Cir[i-1]]]);
Set(1,1,nCir,i-1,disCir-len[edge[Cir[i-1]]]);
mind=min(mind,Query(1));
}
ans=max(ans,mind);
}
int main()
{
freopen("foodshop.in","r",stdin);
freopen("foodshop.out","w",stdout);
read();
FindCircle(1);
Prepare();
Delete_Edge();
printf("%.1lf\n",(double)ans/2);
fclose(stdin);
fclose(stdout);
return 0;
}



  评论这张
 
阅读(2604)| 评论(5)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017