## 【POJ 1737】Connected Graph

_(:з」∠)_

## 【NOI五连测】[D2T1] 啊

1.无名必胜
2.有名必胜
3.先手必胜

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int MAXN = 100000+9;

int n,vout,que[MAXN],type[MAXN],num[MAXN][3];
vector<int> G[MAXN];

char c=getchar(); int buf=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
return buf*f;
}

inline void init(){
for (int i=1;i<=n;i++) G[i].clear(), num[i][0] = num[i][1] = num[i][2] = 0;
for (int i=1;i<=n;i++) type[i] = read() + 1;

int fro,bak; que[fro=bak=1] = 1;
while (fro < n) {
int w = que[bak++];
for (int i=0;i<(int)G[w].size();i++)
que[++fro] = G[w][i];
}
}

void GetAns(int w){
if ((int)G[w].size() == 0) {
if (type[w] == 0) que[++vout] = w;
} else {
int t = num[w][2] - num[w][1];
if (t <= 1 && t >= 0) for (int i=0;i<(int)G[w].size();i++)
GetAns(G[w][i]);
}
}

int main(){
freopen("ah.in","r",stdin);
freopen("ah.out","w",stdout);
int T; cin>>T;
while (T--) {
init();
for (int k=n,i=que[k];k;i=que[--k]){
if ((int)G[i].size() == 0) continue;
else {
for (int j=0;j<(int)G[i].size();j++) num[i][type[G[i][j]]]++;
if (num[i][2] == num[i][1]) type[i] = 0;
else if (num[i][1] > num[i][2]) type[i] = 1;
else type[i] = 2;
}
} if (type[1] == 1) {
int tot = 0; for (int i=1;i<=n;i++) if ((int)G[i].size() == 0 && type[i] == 0) que[++tot] = i;
printf("%d ",tot); for (int i=1;i<=tot;i++) printf("%d ",que[i]); cout<<endl;
} else if (type[1] == 0) {vout = 0, GetAns(1); sort(que+1,que+1+vout); cout<<vout<<' '; for (int i=1;i<=vout;i++) cout<<que[i]<<' '; cout<<endl;}
else printf("-1\n");
}
return 0;
}


## 【NOI六连测】[D1T2] 过河

$$\begin{array}{l} \partial (({V_i} + \sqrt {{u^2} – \frac{{W_i^2}}{{{t^2}}})} \cdot t) = \partial ({V_i} \cdot t) + \partial (\sqrt {{u^2} \cdot {t^2} – W_i^2} )\\ = {V_i} + \partial ({u^2} \cdot {t^2}) \cdot \frac{{0.5}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }} = {V_i} + \frac{{{u^2} \cdot t}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }} \end{array}$$

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#define LD long double
using namespace std;

const int MAXN = 50+9;
const LD EPS = 1e-15;

int n;
LD v[MAXN],w[MAXN],ans[MAXN];
LD disx,MXv,u,t;

inline LD cal(LD k){
LD ret = 0;
for (int i=1;i<=n;i++){
LD r = (k-v[i])*(k-v[i]);
LD t = sqrt(r*w[i]*w[i]/(r*u*u-u*u*u*u));
ans[i] = t; ret += t;
}
return ret;
}

inline double GetAns(){
LD ret = 0;
for (int i=1;i<=n;i++){
LD tmp = sqrt(u*u*ans[i]*ans[i]-w[i]*w[i]);
ret += tmp+v[i]*ans[i];
}
return (double)sqrt(ret*ret+disx*disx);
}

int main(){
freopen("river.in","r",stdin);
freopen("river.out","w",stdout);
scanf("%d",&n); cin>>u>>t;
for (int i=1;i<=n;i++) cin>>w[i]>>v[i],
disx+=w[i], MXv=max(MXv,v[i]);
if (disx/u > t) {printf("-1\n");exit(0);}

LD l=u+MXv,r=1e12,mid;
while (r-l > EPS){
mid = (l+r)/2.0;
if (cal(mid) < t) r = mid;
else l = mid;
}

printf("%.3lf\n",GetAns());
for (int i=1;i<=n;i++) printf("%.3lf ",(double)ans[i]);
return 0;
}