快餐店BZOJ3242--基环树DP
题意：https://www.luogu.com.cn/problem/P1399
思路：
枚举断链，3种情况dp预处理好就行
答案要对max取min（即：所有断完边后的树的直径的最小值）
1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0); 2 #include <cstdio>//sprintf islower isupper 3 #include <cstdlib>//malloc exit strcat itoa system("cls") 4 #include <iostream>//pair 5 #include <fstream>//freopen("C:\Users\13606\Desktop\Input.txt","r",stdin); 6 #include <bitset> 7 //#include <map> 8 //#include<unordered_map> 9 #include <vector> 10 #include <stack> 11 #include <set> 12 #include <string.h>//strstr substr strcat 13 #include <string> 14 #include <time.h>// srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9; 15 #include <cmath> 16 #include <deque> 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less 18 #include <vector>//emplace_back 19 //#include <math.h> 20 #include <cassert> 21 #include <iomanip> 22 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor 23 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare) 24 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation 25 //****************** 26 clock_t __START,__END; 27 double __TOTALTIME; 28 void _MS(){__START=clock();} 29 void _ME(){__END=clock();__TOTALTIME=(double)(__END-__START)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;} 30 //*********************** 31 #define rint register int 32 #define fo(a,b,c) for(rint a=b;a<=c;++a) 33 #define fr(a,b,c) for(rint a=b;a>=c;--a) 34 #define mem(a,b) memset(a,b,sizeof(a)) 35 #define pr printf 36 #define sc scanf 37 #define ls rt<<1 38 #define rs rt<<1|1 39 typedef pair<int,int> PII; 40 typedef vector<int> VI; 41 typedef unsigned long long ull; 42 typedef long long ll; 43 typedef double db; 44 const double E=2.718281828; 45 const double PI=acos(-1.0); 46 const ll INF=(1LL<<60); 47 const int inf=(1<<30); 48 const double ESP=1e-9; 49 const int mod=(int)1e9+7; 50 const int N=(int)1e6+10; 51 #define int long long 52 53 class mymap 54 { 55 public: 56 int tot,cnt_loop; 57 int head[N],in[N],loop[N],deep[N]; 58 bool is[N]; 59 struct 60 { 61 int to,next,dis; 62 }edge[N]; 63 void Init(int n) 64 { 65 tot=cnt_loop=0; 66 for(int i=0;i<=n;++i) 67 head[i]=in[i]=deep[i]=0,is[i]=1; 68 } 69 void add(int from,int to,int dis) 70 { 71 ++tot; 72 edge[tot].to=to; 73 edge[tot].dis=dis; 74 edge[tot].next=head[from]; 75 head[from]=tot; 76 } 77 void get_loop(int n) 78 { 79 queue<int>q; 80 for(int i=1;i<=n;++i) 81 if(in[i]==1) 82 q.push(i); 83 while(!q.empty()) 84 { 85 int now=q.front();q.pop(); 86 is[now]=0; 87 for(int i=head[now];i;i=edge[i].next) 88 { 89 int to=edge[i].to; 90 in[to]--; 91 if(in[to]==1) 92 q.push(to); 93 } 94 } 95 } 96 int temp,max_; 97 void dfs(int fa,int u,int dis) 98 { 99 if(max_<dis)temp=u,max_=dis; 100 for(int i=head[u];i;i=edge[i].next) 101 { 102 int to=edge[i].to; 103 if(is[u]&&is[to])continue; 104 if(to!=fa) 105 dfs(u,to,dis+edge[i].dis); 106 } 107 } 108 }TREE; 109 110 int len[N],val[N]; 111 int maxhalf_l[N],maxhalf_r[N],len_l[N],len_r[N],temp[N]; 112 int lvl[N],lvl_[N],rvr[N],rvr_[N]; 113 114 int num,mark[N]; 115 bool vis[N]; 116 void dfs(int u) 117 { 118 vis[u]=1; 119 mark[++num]=u; 120 for(int i=TREE.head[u];i;i=TREE.edge[i].next) 121 { 122 int to=TREE.edge[i].to; 123 if(!vis[to]&&TREE.is[to]) 124 len[num]=TREE.edge[i].dis,dfs(to); 125 } 126 } 127 128 void solve(int n,int res) 129 { 130 n=TREE.cnt_loop; 131 dfs(TREE.loop[1]); 132 for(int i=TREE.head[mark[n]];i;i=TREE.edge[i].next) 133 { 134 int to=TREE.edge[i].to; 135 if(to==mark[1]) 136 { 137 len[n]=TREE.edge[i].dis; 138 break; 139 } 140 } 141 for(int i=1;i<=n;++i) 142 val[i]=TREE.deep[mark[i]]; 143 //检验 144 //for(int i=1;i<=num;++i)pr("id:%lld len:%lld val:%lld ",mark[i],len[i],val[i]); 145 // 146 int ans=INF; 147 maxhalf_l[1]=val[1]; 148 for(int i=2;i<=num;++i) 149 { 150 len_l[i]=len_l[i-1]+len[i-1]; 151 maxhalf_l[i]=max(maxhalf_l[i-1],len_l[i]+val[i]); 152 } 153 maxhalf_r[n]=val[n]+len[n]; 154 len_r[n]=len[n]; 155 for(int i=n-1;i>=1;--i) 156 { 157 len_r[i]=len_r[i+1]+len[i]; 158 maxhalf_r[i]=max(maxhalf_r[i+1],len_r[i]+val[i]); 159 } 160 for(int i=1;i<=n-1;++i)temp[i]=maxhalf_l[i]+maxhalf_r[i+1]; 161 // 162 // for(int i=1;i<=n;++i)pr("%lld ",mark[i]);cout<<endl; 163 // for(int i=1;i<=n;++i)pr("%lld ",len_l[i]);cout<<endl; 164 // for(int i=1;i<=n;++i)pr("%lld ",len_r[i]);cout<<endl; 165 // 166 lvl[1]=val[1]; 167 for(int i=2;i<=n;++i)lvl[i]=max(lvl[i-1],val[i]-len_l[i]); 168 for(int i=2;i<=n;++i)rvr[i]=max(rvr[i-1],val[i]+len_l[i]+lvl[i-1]); 169 rvr_[n]=val[n]-len[n]; 170 for(int i=n-1;i>=1;--i)rvr_[i]=max(rvr_[i+1],val[i]-len_r[i]); 171 for(int i=n-1;i>=1;--i)lvl_[i]=max(lvl_[i+1],val[i]+len_r[i]+rvr_[i+1]); 172 173 for(int i=1;i<=n;++i) 174 ans=min(ans,max(max(rvr[i],lvl_[i+1]),temp[i])); 175 176 ans=max(ans,res); 177 pr("%lld.%d ",ans/2,(ans&1)?5:0); 178 } 179 180 int32_t main() 181 { 182 freopen("D:\Chrome Download\P1399_15.in","r",stdin); 183 int n; 184 sc("%lld",&n); 185 // for(int i=1;i<=n;++i) 186 // pr("%lld%c ",dp[i]," "[i==n]); 187 188 TREE.Init(n); 189 for(int i=1;i<=n;++i) 190 { 191 int u,v,d; 192 sc("%lld%lld%lld",&u,&v,&d); 193 TREE.add(u,v,d); 194 TREE.add(v,u,d); 195 TREE.in[u]++; 196 TREE.in[v]++; 197 } 198 TREE.get_loop(n); 199 for(int i=1;i<=n;++i) 200 if(TREE.is[i]) 201 TREE.loop[++TREE.cnt_loop]=i; 202 int ans=0; 203 for(int i=1;i<=TREE.cnt_loop;++i) 204 { 205 TREE.max_=-1; 206 TREE.dfs(-1,TREE.loop[i],0); 207 TREE.deep[TREE.loop[i]]=TREE.max_; 208 } 209 for(int i=1;i<=TREE.cnt_loop;++i) 210 { 211 TREE.max_=-1; 212 TREE.dfs(-1,TREE.loop[i],0); 213 TREE.max_=-1; 214 TREE.dfs(-1,TREE.temp,0); 215 ans=max(ans,TREE.max_); 216 } 217 solve(n,ans); 218 return 0; 219 } 220 221 /**************************************************************************************/