更多频道内容在这里查看
爱奇艺用户将能永久保存播放记录
过滤短视频
暂无长视频（电视剧、纪录片、动漫、综艺、电影）播放记录，
您的白银会员还有3天到期啦，续费继续免广告～
手机注册爱奇艺，享受更多云服务
按住视频可进行拖动
把视频贴到Blog或BBS
当前浏览器仅支持手动复制代码
视频地址：
flash地址：
html代码：
通用代码：
通用代码可同时支持电脑和移动设备的分享播放
收藏成功，可进入查看所有收藏列表
方式1：用手机看
用爱奇艺APP或微信扫一扫，在手机上继续观看：
方式2：一键下载至手机
限爱奇艺安卓6.0以上版本
使用微信扫一扫，扫描左侧二维码，下载爱奇艺移动APP
其他安装方式：手机浏览器输入短链接http://71.am/164eL4
下载安装包到本机：&&
设备搜寻中...
请确保您要连接的设备（仅限安卓）登录了同一爱奇艺账号 且安装并开启不低于V6.0以上版本的爱奇艺客户端
连接失败！
请确保您要连接的设备（仅限安卓）登录了同一爱奇艺账号 且安装并开启不低于V6.0以上版本的爱奇艺客户端
部安卓（Android）设备，请点击进行选择
请您在手机端下载爱奇艺移动APP（仅支持安卓客户端）
使用微信扫一扫，下载爱奇艺移动APP
其他安装方式：手机浏览器输入短链接http://71.am/164eL4
下载安装包到本机：&&
爱奇艺云推送
请您在手机端登录爱奇艺移动APP（仅支持安卓客户端）
使用微信扫一扫，下载爱奇艺移动APP
180秒后更新
打开爱奇艺移动APP，点击“我的-扫一扫”，扫描左侧二维码进行登录
没有安装爱奇艺视频最新客户端？
爸爸去哪儿2游戏 立即参与
30秒后自动关闭
EXO-M 采访CUT1 14/04/19
播放量数据：
{{each data}}
抱歉，没有“{{feature}}”的其他视频了.
&正在加载...
&正在加载...
&正在加载...
&正在加载...
&正在加载...
&正在加载...
&正在加载...
&正在加载...
&正在加载...
{{ each data as item index}}
正在打榜(01.04-01.11)
Copyright (C) 2016
All Rights Reserved
您使用浏览器不支持直接复制的功能，建议您使用Ctrl+C或右键全选进行地址复制
安装爱奇艺视频客户端，
马上开始为您下载本片
5秒后自动消失
&li data-elem="tabtitle" data-seq="{{seq}}"&
&a href="javascript:void(0);"&
&span>{{start}}-{{end}}&/span&
&li data-downloadSelect-elem="item" data-downloadSelect-selected="false" data-downloadSelect-tvid="{{tvid}}"&
&a href="javascript:void(0);"&{{pd}}&/a&
选择您要下载的《》剧集：
您使用浏览器不支持直接复制的功能，建议您使用Ctrl+C或右键全选进行地址复制印象二狗 - 每天进步一点点的弱渣
强联通缩点
题目大意：Wiskey通知一群人，联系每个人需要一定的话费，现在想让一些人通知另外一些有对方电话的人，给出有对方电话的对，问Wiskey至少需要通知几个人，至少要花多少话费。
思路：先强联通缩点，求出入度为0的点的个数，即为链数，也就是需要通知的人数，然后再在链上跑这条链上的最小话费。
#include &iostream&
#include &cstring&
#include &cstdio&
#include &algorithm&
const int maxn = 1e3 + 5;
const int maxe = 2e3 + 5;
const int inf = 0x3f3f3f3f;
struct edgeType {
}edge[maxe];
int head[maxn], stack[maxn], DFN[maxn], Low[maxn], Belong[maxn];
// head[]头结点数组,stack[]为栈,DFN[]为深搜次序数组，Belong[]为每个结点所对应的强连通分量标号数组
// Low[u]为u结点或者u的子树结点所能追溯到的最早栈中结点的次序号
int vis[maxn], in[maxn], out[maxn];
// vis[]为是否在栈中的标记数组
int n, m, cnt, scnt, top,
int fee[maxn];
void init() {
scnt = top = tot = 0;
memset(head, -1, sizeof head);
memset(DFN, 0, sizeof DFN);
memset(Low, 0, sizeof Low);
memset(Belong, 0, sizeof Belong);
memset(in, 0, sizeof in);
memset(out, 0, sizeof out);
memset(vis, 0, sizeof vis);
void addedge(int u, int v) {
edge[tot].to =
edge[tot].next = head[u];
head[u] = tot++;
void Tarjan(int v) {
//Tarjan算法求有向图的强连通分量
DFN[v] = Low[v] = ++
//cnt为时间戳
vis[v] = 1;
//标记在栈中
stack[top++] =
for(int e = head[v]; e != -1; e = edge[e].next) {
int j = edge[e].
//v所邻接的边
if(!DFN[j]) { //未被访问
Tarjan(j);
//继续向下找
if(Low[v] & Low[j])
Low[v] = Low[j];
// 更新结点v所能到达的最小次数层
else if(vis[j] && DFN[j] & Low[v]) { //如果j结点在栈内
Low[v] = DFN[j];
if(DFN[v] == Low[v]) { //如果节点v是强连通分量的根
//连通分量标号加1
t = stack[--top];
vis[t] = 0;
//标记不在栈中
Belong[t] =
//出栈结点t属于cnt标号的强连通分量
}while(t != v);
//直到将v从栈中退出
int find_min(int x) {
for(int i = 1; i &= i++) {
if(Belong[i] == x && fee[i] & min) {
min = fee[i];
int main() {
while(scanf("%d %d", &n, &m) != EOF) {
for(int i = 1; i &= i++) {
scanf("%d", &fee[i]);
while(m--) {
scanf("%d %d", &u, &v);
addedge(u, v);
for(int i = 1; i &= i++) {
if(!DFN[i]) {
Tarjan(i);
//计算出度入度
for(int u = 1; u &= u++) {
for(int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].
if(Belong[u] != Belong[v]) {
in[Belong[v]]++;
int pcnt = 0, cost = 0;
for(int i = 1; i &= i++) {
if(in[i] == 0) {
cost += find_min(i);
printf("%d %d\n", pcnt, cost);
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111
#include &iostream&#include &cstring&#include &cstdio&#include &algorithm&using namespace std;&const int maxn = 1e3 + 5;const int maxe = 2e3 + 5;const int inf = 0x3f3f3f3f;&struct edgeType { int to, next;}edge[maxe];&int head[maxn], stack[maxn], DFN[maxn], Low[maxn], Belong[maxn];&&// head[]头结点数组,stack[]为栈,DFN[]为深搜次序数组，Belong[]为每个结点所对应的强连通分量标号数组&& // Low[u]为u结点或者u的子树结点所能追溯到的最早栈中结点的次序号&& int vis[maxn], in[maxn], out[maxn];&&// vis[]为是否在栈中的标记数组&& int n, m, cnt, scnt, top, tot;&&int fee[maxn];&void init() { cnt = 0; scnt = top = tot = 0; memset(head, -1, sizeof head); memset(DFN, 0, sizeof DFN); memset(Low, 0, sizeof Low); memset(Belong, 0, sizeof Belong); memset(in, 0, sizeof in); memset(out, 0, sizeof out); memset(vis, 0, sizeof vis);}&void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;}&void Tarjan(int v) {&&&&&& //Tarjan算法求有向图的强连通分量&&
int min, t;&& DFN[v] = Low[v] = ++tot;&&&&//cnt为时间戳&& vis[v] = 1;&&&&//标记在栈中&&
stack[top++] = v;&&&&&&//入栈&&
for(int e = head[v]; e != -1; e = edge[e].next) {&&&&
int j = edge[e].to;&& //v所邻接的边&&
if(!DFN[j]) { //未被访问
Tarjan(j);&&&&//继续向下找&&
if(Low[v] & Low[j])
Low[v] = Low[j];&&// 更新结点v所能到达的最小次数层&&
else if(vis[j] && DFN[j] & Low[v]) { //如果j结点在栈内
Low[v] = DFN[j];&&
} } if(DFN[v] == Low[v]) { //如果节点v是强连通分量的根
scnt++;&& //连通分量标号加1&&
t = stack[--top];&& //退栈&&
vis[t] = 0;&& //标记不在栈中&&
Belong[t] = scnt;&& //出栈结点t属于cnt标号的强连通分量&&
}while(t != v);&&//直到将v从栈中退出&&
}}&int find_min(int x) { int min = inf; for(int i = 1; i &= n; i++) {
if(Belong[i] == x && fee[i] & min) {
min = fee[i];
} } return min;}&int main() { while(scanf("%d %d", &n, &m) != EOF) {
for(int i = 1; i &= n; i++) {
scanf("%d", &fee[i]);
while(m--) {
scanf("%d %d", &u, &v);
addedge(u, v);
for(int i = 1; i &= n; i++) {&&&&&&&& if(!DFN[i]) {&&&&&&&&
Tarjan(i); &&&&&&&& }&&&& }&&&& //计算出度入度 &&&& for(int u = 1; u &= n; u++) {&&&&
for(int i = head[u]; i != -1; i = edge[i].next) {&&&&
int v = edge[i].to;&&&&
if(Belong[u] != Belong[v]) {&&&&
in[Belong[v]]++;&&&&
}&&&& }&&&& int pcnt = 0, cost = 0;&&&& for(int i = 1; i &= scnt; i++) {&&&&
if(in[i] == 0) {&&&&
cost += find_min(i); &&&&
}&&&& }&&&& printf("%d %d\n", pcnt, cost); } return 0;}
强联通缩点
题目大意：给出点数和边集，问加几条边可是图成为强联通
思路：跑Tarjan，如果已然是个强联通，输出0；否则遍历图，计算出度为0与入度为0两种点的个数，大者即为我们需要建边的数量
#include &iostream&
#include &cstring&
#include &cstdio&
#include &algorithm&
const int maxn = 2e4 + 5;
const int maxe = 5e4 + 5;
struct edgeType {
}edge[maxe && 1];
int head[maxn], stack[maxn], DFN[maxn], Low[maxn], Belong[maxn];
// head[]头结点数组,stack[]为栈,DFN[]为深搜次序数组，Belong[]为每个结点所对应的强连通分量标号数组
// Low[u]为u结点或者u的子树结点所能追溯到的最早栈中结点的次序号
int vis[maxn], in[maxn], out[maxn];
// vis[]为是否在栈中的标记数组
int n, m, cnt, scnt, top,
void init() {
scnt = top = tot = 0;
memset(head, -1, sizeof head);
memset(DFN, 0, sizeof DFN);
memset(Low, 0, sizeof Low);
memset(Belong, 0, sizeof Belong);
memset(in, 0, sizeof in);
memset(out, 0, sizeof out);
memset(vis, 0, sizeof vis);
void addedge(int u, int v) {
edge[tot].to =
edge[tot].next = head[u];
head[u] = tot++;
void Tarjan(int v) {
//Tarjan算法求有向图的强连通分量
DFN[v] = Low[v] = ++
//cnt为时间戳
vis[v] = 1;
//标记在栈中
stack[top++] =
for(int e = head[v]; e != -1; e = edge[e].next) {
int j = edge[e].
//v所邻接的边
if(!DFN[j]) { //未被访问
Tarjan(j);
//继续向下找
if(Low[v] & Low[j])
Low[v] = Low[j];
// 更新结点v所能到达的最小次数层
else if(vis[j] && DFN[j] & Low[v]) { //如果j结点在栈内
Low[v] = DFN[j];
if(DFN[v] == Low[v]) { //如果节点v是强连通分量的根
//连通分量标号加1
t = stack[--top];
vis[t] = 0;
//标记不在栈中
Belong[t] =
//出栈结点t属于cnt标号的强连通分量
}while(t != v);
//直到将v从栈中退出
int main() {
scanf("%d", &cases);
while(cases--) {
scanf("%d %d", &n, &m);
while(m--) {
scanf("%d %d", &u, &v);
addedge(u, v);
for(int i = 1; i &= i++) {
if(!DFN[i]) {
Tarjan(i);
if(scnt == 1) {
puts("0");
//计算出度入度
for(int u = 1; u &= u++) {
for(int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].
if(Belong[u] != Belong[v]) {
in[Belong[v]]++;
out[Belong[u]]++;
int a = 0, b = 0;
for(int i = 1; i &= i++) {
if(in[i] == 0) a++;
if(out[i] == 0) b++;
printf("%d\n", max(a, b));
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102
#include &iostream&#include &cstring&#include &cstdio&#include &algorithm&using namespace std; const int maxn = 2e4 + 5;const int maxe = 5e4 + 5; struct edgeType { int to, next;}edge[maxe && 1]; int head[maxn], stack[maxn], DFN[maxn], Low[maxn], Belong[maxn];&&// head[]头结点数组,stack[]为栈,DFN[]为深搜次序数组，Belong[]为每个结点所对应的强连通分量标号数组&& // Low[u]为u结点或者u的子树结点所能追溯到的最早栈中结点的次序号&& int vis[maxn], in[maxn], out[maxn];&&// vis[]为是否在栈中的标记数组&& int n, m, cnt, scnt, top, tot;&& void init() { cnt = 0; scnt = top = tot = 0; memset(head, -1, sizeof head); memset(DFN, 0, sizeof DFN); memset(Low, 0, sizeof Low); memset(Belong, 0, sizeof Belong); memset(in, 0, sizeof in); memset(out, 0, sizeof out); memset(vis, 0, sizeof vis);} void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;} void Tarjan(int v) {&&&&&& //Tarjan算法求有向图的强连通分量&&
int min, t;&& DFN[v] = Low[v] = ++tot;&&&&//cnt为时间戳&& vis[v] = 1;&&&&//标记在栈中&&
stack[top++] = v;&&&&&&//入栈&&
for(int e = head[v]; e != -1; e = edge[e].next) {&&&&
int j = edge[e].to;&& //v所邻接的边&&
if(!DFN[j]) { //未被访问
Tarjan(j);&&&&//继续向下找&&
if(Low[v] & Low[j])
Low[v] = Low[j];&&// 更新结点v所能到达的最小次数层&&
else if(vis[j] && DFN[j] & Low[v]) { //如果j结点在栈内
Low[v] = DFN[j];&&
} } if(DFN[v] == Low[v]) { //如果节点v是强连通分量的根
scnt++;&& //连通分量标号加1&&
t = stack[--top];&& //退栈&&
vis[t] = 0;&& //标记不在栈中&&
Belong[t] = scnt;&& //出栈结点t属于cnt标号的强连通分量&&
}while(t != v);&&//直到将v从栈中退出&&
}} int main() { int cases; scanf("%d", &cases); while(cases--) {
scanf("%d %d", &n, &m);
while(m--) {
scanf("%d %d", &u, &v);
addedge(u, v);
for(int i = 1; i &= n; i++) {&&&&&&&& if(!DFN[i]) {&&&&&&&&
Tarjan(i); &&&&&&&& }&&&& }&&&& if(scnt == 1) {&&&&
puts("0");&&&&
continue ;&&&& }&&&& //计算出度入度 &&&& for(int u = 1; u &= n; u++) {&&&&
for(int i = head[u]; i != -1; i = edge[i].next) {&&&&
int v = edge[i].to;&&&&
if(Belong[u] != Belong[v]) {&&&&
in[Belong[v]]++;&&&&
out[Belong[u]]++;&&&&
}&&&& }&&&& int a = 0, b = 0;&&&& for(int i = 1; i &= scnt; i++) {&&&&
if(in[i] == 0) a++;&&&&
if(out[i] == 0) b++;&&&& }&&&& printf("%d\n", max(a, b)); } return 0;}
Kosaraju Tarjan 强联通
题目大意：求强联通分量结点大于1的个数
思路：Tarjan or Kosaraju　
#include &iostream&
#include &cstring&
#include &cstdio&
#include &algorithm&
const int maxn = 1e4 + 5;
const int maxm = 1e5 + 5;
struct edgeType {
}edge[maxm];
int first[maxn], stack[maxn], DFN[maxn], Low[maxn], Belong[maxm];
// first[]头结点数组,stack[]为栈,DFN[]为深搜次序数组，Belong[]为每个结点所对应的强连通分量标号数组
// Low[u]为u结点或者u的子树结点所能追溯到的最早栈中结点的次序号
int instack[10010];
// instack[]为是否在栈中的标记数组
int n, m, cnt, scnt, top,
void init() {
scnt = top = tot = 0;
memset(first, -1, sizeof first);
memset(DFN, 0, sizeof DFN);
void addedge(int u, int v) {
edge[tot].to =
edge[tot].next = first[u];
first[u] = tot++;
void Tarjan(int v) {
//Tarjan算法求有向图的强连通分量
DFN[v] = Low[v] = ++
//cnt为时间戳
instack[v] = 1;
//标记在栈中
stack[top++] =
for(int e = first[v]; e != -1; e = edge[e].next) {
int j = edge[e].
//v所邻接的边
if(!DFN[j]) { //未被访问
Tarjan(j);
//继续向下找
if(Low[v] & Low[j])
Low[v] = Low[j];
// 更新结点v所能到达的最小次数层
else if(instack[j] && DFN[j] & Low[v]) { //如果j结点在栈内
Low[v] = DFN[j];
if(DFN[v] == Low[v]) { //如果节点v是强连通分量的根
//连通分量标号加1
t = stack[--top];
instack[t] = 0;
//标记不在栈中
Belong[t] =
//出栈结点t属于cnt标号的强连通分量
}while(t != v);
//直到将v从栈中退出
int main() {
while(scanf("%d %d", &n, &m) != EOF) {
if(n == 0 && m == 0) {
while(m--) {
scanf("%d %d", &u, &v);
addedge(u, v);
int ans = 0;
for(int i = 1; i &= i++) {
if(!DFN[i]) {
Tarjan(i);
if(scnt & 1) ans++;
printf("%d\n", ans);
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
#include &iostream&#include &cstring&#include &cstdio&#include &algorithm&using namespace std;&const int maxn = 1e4 + 5;const int maxm = 1e5 + 5;&struct edgeType { int to, next;}edge[maxm];&int first[maxn], stack[maxn], DFN[maxn], Low[maxn], Belong[maxm];&&// first[]头结点数组,stack[]为栈,DFN[]为深搜次序数组，Belong[]为每个结点所对应的强连通分量标号数组&& // Low[u]为u结点或者u的子树结点所能追溯到的最早栈中结点的次序号&& int instack[10010];&&// instack[]为是否在栈中的标记数组&& int n, m, cnt, scnt, top, tot;&&&void init() { cnt = 0; scnt = top = tot = 0; memset(first, -1, sizeof first); memset(DFN, 0, sizeof DFN);}&void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = first[u]; first[u] = tot++;}&void Tarjan(int v) {&&&&&& //Tarjan算法求有向图的强连通分量&&
int min, t;&& DFN[v] = Low[v] = ++tot;&&&&//cnt为时间戳&& instack[v] = 1;&&&&//标记在栈中&&
stack[top++] = v;&&&&&&//入栈&&
for(int e = first[v]; e != -1; e = edge[e].next) {&&&&
int j = edge[e].to;&& //v所邻接的边&&
if(!DFN[j]) { //未被访问
Tarjan(j);&&&&//继续向下找&&
if(Low[v] & Low[j])
Low[v] = Low[j];&&// 更新结点v所能到达的最小次数层&&
else if(instack[j] && DFN[j] & Low[v]) { //如果j结点在栈内
Low[v] = DFN[j];&&
} } if(DFN[v] == Low[v]) { //如果节点v是强连通分量的根
scnt++;&& //连通分量标号加1&&
t = stack[--top];&& //退栈&&
instack[t] = 0;&& //标记不在栈中&&
Belong[t] = scnt;&& //出栈结点t属于cnt标号的强连通分量&&
}while(t != v);&&//直到将v从栈中退出&&
}&&}&&&int main() { while(scanf("%d %d", &n, &m) != EOF) {
if(n == 0 && m == 0) {
while(m--) {
scanf("%d %d", &u, &v);
addedge(u, v);
int ans = 0;
for(int i = 1; i &= n; i++) {&&&&&&&& if(!DFN[i]) {&&&&&&&&
Tarjan(i);&&&&&&&&
if(scnt & 1) ans++;&&&&&&&& }&&&& }&&&& printf("%d\n", ans); } return 0;}
#include&stdio.h&
#include&string.h&
#include&iostream&
#define MAXN 10005 //结点的最大数
struct Node
}edge1[MAXN*5],edge2[MAXN*5];
//edge1用来存原图G，edge2用来存GT，即逆图
//都是用邻接表来储存的图，
int head1[MAXN];//原图的邻接表的头结点
int head2[MAXN];//逆图的邻接表的头结点
int mark1[MAXN],mark2[MAXN];
int tot1,tot2;
int cnt1,cnt2,st[MAXN],belong[MAXN];
int num,setNum[MAXN];
struct Edge
}e[MAXN*5];//储存边
void add(int a,int b)//添加边a-&b，在原图和逆图都需要添加
edge1[tot1].to=b;edge1[tot1].next=head1[a];head1[a]=tot1++;//邻接表存的原图
edge2[tot2].to=a;edge2[tot2].next=head2[b];head2[b]=tot2++;//邻接表存的逆图
void DFS1(int x)//深度搜索原图
mark1[x]=1;
for(int i=head1[x];i!=-1;i=edge1[i].next)
if(!mark1[edge1[i].to])
DFS1(edge1[i].to);
st[cnt1++]=x;//st数组是按照完成时间从小到大排序的
void DFS2(int x)//深度搜索逆图
mark2[x]=1;
belong[x]=cnt2;
for(int i=head2[x];i!=-1;i=edge2[i].next)
if(!mark2[edge2[i].to]) DFS2(edge2[i].to);
int main()
while(scanf("%d%d",&n,&m)!=EOF)
tot1=tot2=1;
for(int i=1;i&=n;i++)//初始化
head1[i]=head2[i]=-1;
mark1[i]=mark2[i]=0;
for(int i=1;i&=m;i++)
scanf("%d%d",&w,&v);
e[i].l=w;e[i].r=v;//储存边
add(w,v);//建立邻接表
cnt1=cnt2=1;
for(int i=1;i&=n;i++)
if(!mark1[i])DFS1(i);
for(int i=cnt1-1;i&=1;i--)
if(!mark2[st[i]])
DFS2(st[i]);
setNum[cnt2++]=
int cnt=0;
for(int i=1;i&cnt2;i++)
if(setNum[i]&=2)cnt++;
printf("%d\n",cnt);
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182
#include&stdio.h&#include&string.h&#include&iostream&using namespace std;#define MAXN 10005 //结点的最大数struct Node{&&&&int to,next;}edge1[MAXN*5],edge2[MAXN*5];//edge1用来存原图G，edge2用来存GT，即逆图//都是用邻接表来储存的图，int head1[MAXN];//原图的邻接表的头结点int head2[MAXN];//逆图的邻接表的头结点int mark1[MAXN],mark2[MAXN];int tot1,tot2;int cnt1,cnt2,st[MAXN],belong[MAXN];int num,setNum[MAXN];struct Edge{&&&&int l,r;}e[MAXN*5];//储存边 &void add(int a,int b)//添加边a-&b，在原图和逆图都需要添加{&&&&edge1[tot1].to=b;edge1[tot1].next=head1[a];head1[a]=tot1++;//邻接表存的原图&&&&edge2[tot2].to=a;edge2[tot2].next=head2[b];head2[b]=tot2++;//邻接表存的逆图 }&& void DFS1(int x)//深度搜索原图 {&&&&mark1[x]=1;&&&&for(int i=head1[x];i!=-1;i=edge1[i].next)&&&&&&&&&&if(!mark1[edge1[i].to])&&DFS1(edge1[i].to);&&&&st[cnt1++]=x;//st数组是按照完成时间从小到大排序的 }&&&&&&void DFS2(int x)//深度搜索逆图{&&&&mark2[x]=1;&&&&num++;&&&&belong[x]=cnt2;&&&&for(int i=head2[x];i!=-1;i=edge2[i].next)&&&&&& if(!mark2[edge2[i].to]) DFS2(edge2[i].to);}&&&& int main(){&&&&int n,m;&&&&while(scanf("%d%d",&n,&m)!=EOF)&&&&{&&&&&&&&tot1=tot2=1;&&&&&&&&for(int i=1;i&=n;i++)//初始化 &&&&&&&&{&&&&&&&&&&&&head1[i]=head2[i]=-1;&&&&&&&&&&&&mark1[i]=mark2[i]=0;&&&&&&&&}&&&&&&&&for(int i=1;i&=m;i++)&&&&&&&&{&&&&&&&&&&&&int w,v;&&&&&&&&&&&&scanf("%d%d",&w,&v);&&&&&&&&&&&&e[i].l=w;e[i].r=v;//储存边 &&&&&&&&&&&&add(w,v);//建立邻接表 &&&&&&&&}&&&&&&&&&&&&&&&&cnt1=cnt2=1;&&&&&&&&for(int i=1;i&=n;i++)&&&&&&&&{&&&&&&&&&&&&if(!mark1[i])DFS1(i);&&&&&&&&}&&&&&&&&&&&&for(int i=cnt1-1;i&=1;i--)&&&&&&&&{&&&&&&&&&&&&if(!mark2[st[i]])&&&&&&&&&&&&{&&&&&&&&&&&&&&&&num=0;&&&&&&&&&&&&&&&&DFS2(st[i]);&&&&&&&&&&&&&&&&setNum[cnt2++]=num;&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&&&&&&&&&int cnt=0;&&&&&&&&for(int i=1;i&cnt2;i++)&&&&&&&&&&&&if(setNum[i]&=2)cnt++;&&&&&&&&printf("%d\n",cnt);&&&& &&&&}&&&&&&&&return 0;}&&&&
题目大意：给出点数和有向边集，当强连通分量为1的时候输出Yes否者输出No；
思路：套Tarjan算法
#include &iostream&
#include &cstring&
#include &cstdio&
#include &algorithm&
const int maxn = 1e4 + 5;
const int maxm = 1e5 + 5;
struct edgeType {
}edge[maxm];
int first[maxn], stack[maxn], DFN[maxn], Low[maxn], Belong[maxm];
// first[]头结点数组,stack[]为栈,DFN[]为深搜次序数组，Belong[]为每个结点所对应的强连通分量标号数组
// Low[u]为u结点或者u的子树结点所能追溯到的最早栈中结点的次序号
int instack[10010];
// instack[]为是否在栈中的标记数组
int n, m, cnt, scnt, top,
void init() {
scnt = top = tot = 0;
memset(first, -1, sizeof first);
memset(DFN, 0, sizeof DFN);
void addedge(int u, int v) {
edge[tot].to =
edge[tot].next = first[u];
first[u] = tot++;
void Tarjan(int v) {
//Tarjan算法求有向图的强连通分量
DFN[v] = Low[v] = ++
//cnt为时间戳
instack[v] = 1;
//标记在栈中
stack[top++] =
for(int e = first[v]; e != -1; e = edge[e].next) {
int j = edge[e].
//v所邻接的边
if(!DFN[j]) { //未被访问
Tarjan(j);
//继续向下找
if(Low[v] & Low[j])
Low[v] = Low[j];
// 更新结点v所能到达的最小次数层
else if(instack[j] && DFN[j] & Low[v]) { //如果j结点在栈内
Low[v] = DFN[j];
if(DFN[v] == Low[v]) { //如果节点v是强连通分量的根
//连通分量标号加1
t = stack[--top];
instack[t] = 0;
//标记不在栈中
Belong[t] =
//出栈结点t属于cnt标号的强连通分量
}while(t != v);
//直到将v从栈中退出
int main() {
while(scanf("%d %d", &n, &m) != EOF) {
if(n == 0 && m == 0) {
while(m--) {
scanf("%d %d", &u, &v);
addedge(u, v);
for(int i = 1; i &= i++) {
if(!DFN[i]) {
Tarjan(i);
if(scnt == 1) printf("Yes\n");
else printf("No\n");
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
#include &iostream&#include &cstring&#include &cstdio&#include &algorithm&using namespace std;&const int maxn = 1e4 + 5;const int maxm = 1e5 + 5;&struct edgeType { int to, next;}edge[maxm];&int first[maxn], stack[maxn], DFN[maxn], Low[maxn], Belong[maxm];&&// first[]头结点数组,stack[]为栈,DFN[]为深搜次序数组，Belong[]为每个结点所对应的强连通分量标号数组&& // Low[u]为u结点或者u的子树结点所能追溯到的最早栈中结点的次序号&& int instack[10010];&&// instack[]为是否在栈中的标记数组&& int n, m, cnt, scnt, top, tot;&&&void init() { cnt = 0; scnt = top = tot = 0; memset(first, -1, sizeof first); memset(DFN, 0, sizeof DFN);}&void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = first[u]; first[u] = tot++;}&void Tarjan(int v) {&&&&&& //Tarjan算法求有向图的强连通分量&&
int min, t;&& DFN[v] = Low[v] = ++tot;&&&&//cnt为时间戳&& instack[v] = 1;&&&&//标记在栈中&&
stack[top++] = v;&&&&&&//入栈&&
for(int e = first[v]; e != -1; e = edge[e].next) {&&&&
int j = edge[e].to;&& //v所邻接的边&&
if(!DFN[j]) { //未被访问
Tarjan(j);&&&&//继续向下找&&
if(Low[v] & Low[j])
Low[v] = Low[j];&&// 更新结点v所能到达的最小次数层&&
else if(instack[j] && DFN[j] & Low[v]) { //如果j结点在栈内
Low[v] = DFN[j];&&
} } if(DFN[v] == Low[v]) { //如果节点v是强连通分量的根
scnt++;&& //连通分量标号加1&&
t = stack[--top];&& //退栈&&
instack[t] = 0;&& //标记不在栈中&&
Belong[t] = scnt;&& //出栈结点t属于cnt标号的强连通分量&&
}while(t != v);&&//直到将v从栈中退出&&
}&&}&&&int main() { while(scanf("%d %d", &n, &m) != EOF) {
if(n == 0 && m == 0) {
while(m--) {
scanf("%d %d", &u, &v);
addedge(u, v);
for(int i = 1; i &= n; i++) {&&&&&&&& if(!DFN[i]) {&&&&&&&&
Tarjan(i); &&&&&&&& }&&&& }&&&& if(scnt == 1) printf("Yes\n");&&&& else printf("No\n"); } return 0;}
2-SAT 二分图 双联通 强联通 网络流
题目大意：给一棵树，并给定各个点权的值，然后有3种操作：I C1 C2 K: 把C1与C2的路径上的所有点权值加上K；D C1 C2 K：把C1与C2的路径上的所有点权值减去K；Q C：查询节点编号为C的权值；
思路：典型题
#pragma comment(linker, "/STACK:,")
#include &iostream&
#include &cstring&
#include &algorithm&
#include &stdio.h&
#include &vector&
const int N=50010;
int n,m,Q;
int num[N],siz[N],top[N],son[N];
int dep[N],tid[N],rank[N],fa[N];
int head[N],to[2*N],next[2*N],
void Init()
memset(head,-1,sizeof(head));
memset(son,-1,sizeof(son));
void addedge(int u,int v)
to[edge]=v,next[edge]=head[u],head[u]=edge++;
to[edge]=u,next[edge]=head[v],head[v]=edge++;
//树链剖分部分
void dfs1(int u,int father,int d)
for(int i=head[u];~i;i=next[i])
int v=to[i];
if(v!=father)
dfs1(v,u,d+1);
siz[u]+=siz[v];
if(son[u]==-1||siz[v]&siz[son[u]])
void dfs2(int u,int tp)
rank[tid[u]]=u;
if(son[u]==-1)
dfs2(son[u],tp);
for(int i=head[u];~i;i=next[i])
int v=to[i];
if(v!=son[u]&&v!=fa[u])
dfs2(v,v);
//线段树部分
#define lson l,mid,rt&&1
#define rson mid+1,r,rt&&1|1
int sum[4*N],col[4*N];
void PushUP(int rt)
sum[rt]=max(sum[rt&&1],sum[rt&&1|1]);
void PushDown(int rt,int m)
if(col[rt])
col[rt&&1]+=col[rt];
col[rt&&1|1]+=col[rt];
sum[rt&&1]+=(m-(m&&1))*col[rt];
sum[rt&&1|1]+=(m&&1)*col[rt];
col[rt]=0;
void Build(int l,int r,int rt)
col[rt]=0;
sum[rt]=num[rank[l]];
int mid=(l+r)&&1;
Build(lson);
Build(rson);
PushUP(rt);
void Update(int L,int R,int v,int l,int r,int rt)
if(L&=l&&R&=r)
col[rt]+=v;
sum[rt]+=v*(r-l+1);
PushDown(rt,r-l+1);
int mid=(l+r)&&1;
if(L&=mid)
Update(L,R,v,lson);
Update(L,R,v,rson);
PushUP(rt);
int Query(int l,int r,int rt,int val)
return sum[rt];
PushDown(rt,r-l+1);
int mid=(l+r)&&1;
int ret=0;
if(val&=mid) ret=Query(lson,val);
ret=Query(rson,val);
PushUP(rt);
void Change(int x,int y,int val)
while(top[x]!=top[y])
if(dep[top[x]]&dep[top[y]]) swap(x,y);
Update(tid[top[x]],tid[x],val,1,n,1);
x=fa[top[x]];
if(dep[x]&dep[y]) swap(x,y);
Update(tid[x],tid[y],val,1,n,1);
int main()
char oper[5];
int a,b,c;
while(~scanf("%d%d%d",&n,&m,&Q))
for(int i=1;i&=n;i++)
scanf("%d",&num[i]);
for(int i=1;i&=m;i++)
scanf("%d%d",&a,&b);
addedge(a,b);
dfs1(1,0,0);
dfs2(1,1);
Build(1,n,1);
while(Q--)
scanf("%s",oper);
if(oper[0]=='Q')
scanf("%d",&a);
printf("%d\n",Query(1,n,1,tid[a]));
scanf("%d%d%d",&a,&b,&c);
if(oper[0]=='D') c=-c;
Change(a,b,c);
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179
#pragma comment(linker, "/STACK:,")&&#include &iostream&&&#include &cstring&&&#include &algorithm&&&#include &stdio.h&&&#include &vector&&&&&using namespace std;&&const int N=50010;&&&&int n,m,Q;&&int tim;&&&&int num[N],siz[N],top[N],son[N];&&int dep[N],tid[N],rank[N],fa[N];&&int head[N],to[2*N],next[2*N],edge;&&&&void Init()&&{&&&&&&memset(head,-1,sizeof(head));&&&&&&memset(son,-1,sizeof(son));&&&&&&tim=0;&&&&&&edge=0;&&}&&&&void addedge(int u,int v)&&{&&&&&&to[edge]=v,next[edge]=head[u],head[u]=edge++;&&&&&&to[edge]=u,next[edge]=head[v],head[v]=edge++;&&}&&&&//树链剖分部分&&void dfs1(int u,int father,int d)&&{&&&&&&dep[u]=d;&&&&&&fa[u]=father;&&&&&&siz[u]=1;&&&&&&for(int i=head[u];~i;i=next[i])&&&&&&{&&&&&&&&&&int v=to[i];&&&&&&&&&&if(v!=father)&&&&&&&&&&{&&&&&&&&&&&&&&dfs1(v,u,d+1);&&&&&&&&&&&&&&siz[u]+=siz[v];&&&&&&&&&&&&&&if(son[u]==-1||siz[v]&siz[son[u]])&&&&&&&&&&&&&&&&&&son[u]=v;&&&&&&&&&&}&&&&&&}&&}&&&&void dfs2(int u,int tp)&&{&&&&&&top[u]=tp;&&&&&&tid[u]=++tim;&&&&&&rank[tid[u]]=u;&&&&&&if(son[u]==-1) return;&&&&&&dfs2(son[u],tp);&&&&&&for(int i=head[u];~i;i=next[i])&&&&&&{&&&&&&&&&&int v=to[i];&&&&&&&&&&if(v!=son[u]&&v!=fa[u])&&&&&&&&&&&&&&dfs2(v,v);&&&&&&}&&}&&&&//线段树部分&&#define lson l,mid,rt&&1&&#define rson mid+1,r,rt&&1|1&&&&int sum[4*N],col[4*N];&&&&void PushUP(int rt)&&{&&&&&&sum[rt]=max(sum[rt&&1],sum[rt&&1|1]);&&}&&&&void PushDown(int rt,int m)&&{&&&&&&if(col[rt])&&&&&&{&&&&&&&&&&col[rt&&1]+=col[rt];&&&&&&&&&&col[rt&&1|1]+=col[rt];&&&&&&&&&&sum[rt&&1]+=(m-(m&&1))*col[rt];&&&&&&&&&&sum[rt&&1|1]+=(m&&1)*col[rt];&&&&&&&&&&col[rt]=0;&&&&&&}&&}&&&&void Build(int l,int r,int rt)&&{&&&&&&col[rt]=0;&&&&&&if(l==r)&&&&&&{&&&&&&&&&&sum[rt]=num[rank[l]];&&&&&&&&&&return;&&&&&&}&&&&&&int mid=(l+r)&&1;&&&&&&Build(lson);&&&&&&Build(rson);&&&&&&PushUP(rt);&&}&&&&void Update(int L,int R,int v,int l,int r,int rt)&&{&&&&&&if(L&=l&&R&=r)&&&&&&{&&&&&&&&&&col[rt]+=v;&&&&&&&&&&sum[rt]+=v*(r-l+1);&&&&&&&&&&return;&&&&&&}&&&&&&PushDown(rt,r-l+1);&&&&&&int mid=(l+r)&&1;&&&&&&if(L&=mid)&&&&&&&&&&Update(L,R,v,lson);&&&&&&if(R&mid)&&&&&&&&&&Update(L,R,v,rson);&&&&&&PushUP(rt);&&}&&&&int Query(int l,int r,int rt,int val)&&{&&&&&&if(l==r)&&&&&&&&&&return sum[rt];&&&&&&PushDown(rt,r-l+1);&&&&&&int mid=(l+r)&&1;&&&&&&int ret=0;&&&&&&if(val&=mid) ret=Query(lson,val);&&&&&&else&&&&&&&& ret=Query(rson,val);&&&&&&PushUP(rt);&&&&&&return ret;&&}&&&&void Change(int x,int y,int val)&&{&&&&&&while(top[x]!=top[y])&&&&&&{&&&&&&&&&&if(dep[top[x]]&dep[top[y]]) swap(x,y);&&&&&&&&&&Update(tid[top[x]],tid[x],val,1,n,1);&&&&&&&&&&x=fa[top[x]];&&&&&&}&&&&&&if(dep[x]&dep[y]) swap(x,y);&&&&&&Update(tid[x],tid[y],val,1,n,1);&&}&&&&int main()&&{&&&&&&char oper[5];&&&&&&int a,b,c;&&&&&&while(~scanf("%d%d%d",&n,&m,&Q))&&&&&&{&&&&&&&&&&Init();&&&&&&&&&&for(int i=1;i&=n;i++)&&&&&&&&&&&& scanf("%d",&num[i]);&&&&&&&&&&for(int i=1;i&=m;i++)&&&&&&&&&&{&&&&&&&&&&&&&&scanf("%d%d",&a,&b);&&&&&&&&&&&&&&addedge(a,b);&&&&&&&&&&}&&&&&&&&&&dfs1(1,0,0);&&&&&&&&&&dfs2(1,1);&&&&&&&&&&Build(1,n,1);&&&&&&&&&&while(Q--)&&&&&&&&&&{&&&&&&&&&&&&&&scanf("%s",oper);&&&&&&&&&&&&&&if(oper[0]=='Q')&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&scanf("%d",&a);&&&&&&&&&&&&&&&&&&printf("%d\n",Query(1,n,1,tid[a]));&&&&&&&&&&&&&&}&&&&&&&&&&&&&&else&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&scanf("%d%d%d",&a,&b,&c);&&&&&&&&&&&&&&&&&&if(oper[0]=='D') c=-c;&&&&&&&&&&&&&&&&&&Change(a,b,c);&&&&&&&&&&&&&&}&&&&&&&&&&}&&&&&&}&&&&&&return 0;&&}&&
模板现学过的。。
题目大意：两个人各有N个士兵，每个士兵有血量和攻击力，一轮攻击后两士兵同时结算生命值，问A是否能将B的士兵全部打败；
思路：若A的士兵能严格将B的士兵打死，自己存活，则建边g[a][b]，跑匈牙利算法。
#include &iostream&
#include &cstdio&
#include &cstring&
#include &algorithm&
const int maxn = 100 + 5;
int uN, vN;
int g[maxn][maxn];
bool used[maxn];
int linker[maxn];
bool dfs(int u) {
for(int v = 0; v & vN; v++) {
if(g[u][v] && !used[v]) {
if(linker[v] == -1 || dfs(linker[v])) {
linker[v] =
struct person {
}a[maxn], b[maxn];
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(int i = 1; i &= i++) {
scanf("%d %d", &a[i].l, &a[i].a);
for(int i = 1; i &= i++) {
scanf("%d %d", &b[i].l, &b[i].a);
memset(g, 0, sizeof g);
for(int i = 1; i &= i++) {
for(int j = 1; j &= j++) {
int lifea = a[i].l - b[j].a;
int lifeb = b[j].l - a[i].a;
if(lifea & 0 && lifeb &= 0) {
g[i-1][j-1] = 1;
int res = 0;
memset(linker, -1, sizeof(linker));
for(int u = 0; u & uN; u++) {
memset(used, false, sizeof used);
if(dfs(u)) res++;
//cout && res &&
if(res == n) {
printf("Yes\n");
printf("No\n");
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
#include &iostream&#include &cstdio&#include &cstring&#include &algorithm&using namespace std;&const int maxn = 100 + 5;int uN, vN;int g[maxn][maxn];bool used[maxn];int linker[maxn];&bool dfs(int u) { for(int v = 0; v & vN; v++) {
if(g[u][v] && !used[v]) {
used[v] = true;
if(linker[v] == -1 || dfs(linker[v])) {
linker[v] = u;
return true;
} } return false;}&struct person { int l, a;}a[maxn], b[maxn];&int main() { int t; scanf("%d", &t); while(t--) {
scanf("%d", &n);
uN = vN = n;
for(int i = 1; i &= n; i++) {
scanf("%d %d", &a[i].l, &a[i].a);
for(int i = 1; i &= n; i++) {
scanf("%d %d", &b[i].l, &b[i].a);
memset(g, 0, sizeof g);
for(int i = 1; i &= n; i++) {
for(int j = 1; j &= n; j++) {
int lifea = a[i].l - b[j].a;
int lifeb = b[j].l - a[i].a;
if(lifea & 0 && lifeb &= 0) {
g[i-1][j-1] = 1;
int res = 0;
memset(linker, -1, sizeof(linker));
for(int u = 0; u & uN; u++) {
memset(used, false, sizeof used);
if(dfs(u)) res++;
//cout && res &&
if(res == n) {
printf("Yes\n");
printf("No\n");
} } return 0;}
题目大意：有N个人按照1~N排序，每个人有活跃度，N个人中又有下属与直接上司的关系，下属不与直接上司在一起，问如何取到最多的活跃度。
思路：建边集，每个结点维护两个值dp[maxn][0]与dp[maxn][1]，分别代表不取和取。
#include &iostream&
#include &cstdio&
#include &cstring&
#include &algorithm&
const int maxn = 6e4 + 5;
int dp[maxn][2], head[maxn];
int rt[maxn], le[maxn],
struct edge {
}e[maxn && 1];
void addedge(int u, int v) {
e[top].to =
e[top].next = head[u];
head[u] = top++;
void dfs(int root) {
if(le[root]) {
dp[root][0] = 0;
for(int i = head[root]; i != -1; i = e[i].next) {
int son = e[i].
dp[root][0] += max(dp[son][0], dp[son][1]);
dp[root][1] += dp[son][0];
void init() {
memset(head, -1, sizeof head);
int main() {
while(scanf("%d", &n) != EOF) {
for(int i = 1; i &= i++) {
scanf("%d", &dp[i][1]);
le[i] = rt[i] = 1;
while(scanf("%d %d", &u, &v), u || v) {
le[v] = rt[u] = 0;
addedge(v, u);
for(int i = 1; i &= i++) {
if(rt[i]) {
dfs(root);
printf("%d\n", max(dp[root][0], dp[root][1]));
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
#include &iostream&#include &cstdio&#include &cstring&#include &algorithm&using namespace std;&const int maxn = 6e4 + 5;int dp[maxn][2], head[maxn];int rt[maxn], le[maxn], top;&struct edge { int to, next;}e[maxn && 1];&void addedge(int u, int v) { e[top].to = v; e[top].next = head[u]; head[u] = top++;}&void dfs(int root) { if(le[root]) {
dp[root][0] = 0;
return; } for(int i = head[root]; i != -1; i = e[i].next) {
int son = e[i].to;
dp[root][0] += max(dp[son][0], dp[son][1]);
dp[root][1] += dp[son][0]; }}&void init() { memset(head, -1, sizeof head); top = 0;}&int main() { int n; while(scanf("%d", &n) != EOF) {
for(int i = 1; i &= n; i++) {
scanf("%d", &dp[i][1]);
le[i] = rt[i] = 1;
while(scanf("%d %d", &u, &v), u || v) {
le[v] = rt[u] = 0;
addedge(v, u);
for(int i = 1; i &= n; i++) {
if(rt[i]) {
dfs(root);
printf("%d\n", max(dp[root][0], dp[root][1])); } return 0;}
题目大意：给出一块的正方形，同时正方形上有不可路经的圆，现在要从正方形的左侧走到右侧，求能否实现，能的话输出最矮的起点和终点。
思路：从有与上边界接壤的圆开始，向下搜索与此圆相交的圆，如果能走到下边界，则是无法实现的。
#include &iostream&
#include &cstdio&
#include &cstring&
#include &cmath&
#include &algorithm&
const int N = 1000 + 5;
struct Circle {
void read() {
scanf("%d %d %d", &x, &y, &r);
double ans1, ans2;
int n, vis[N];
bool can(Circle a, Circle b) {
int dx = a.x - b.x;
int dy = a.y - b.y;
return dx*dx + dy*dy - (a.r + b.r)*(a.r + b.r) &= 0;
bool dfs(int u) {
vis[u] = 1;
if(c[u].y - c[u].r &= 0)
if(c[u].x - c[u].r &= 0)
ans1 = min(ans1, c[u].y - sqrt(c[u].r*c[u].r - c[u].x*c[u].x));
if(1000 - c[u].x - c[u].r &= 0)
ans2 = min(ans2, c[u].y - sqrt(c[u].r*c[u].r - (1000 - c[u].x)*(1000 - c[u].x)));
for(int i = 0; i & i++) {
if(!vis[i]) {
if (can(c[u], c[i]))
if (!dfs(i))
void solve() {
ans1 = ans2 = 1000;
for(int i = 0; i & i++) {
if(!vis[i] && c[i].y + c[i].r&=1000) {
if(!dfs(i)) {
puts("IMPOSSIBLE");
printf("0.00 %.2lf 1000.00 %.2lf\n", ans1, ans2);
int main() {
while (~scanf("%d", &n)) {
memset(vis, 0, sizeof(vis));
for(int i = 0; i & i++) {
c[i].read();
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465
#include &iostream&#include &cstdio&#include &cstring&#include &cmath&#include &algorithm&using namespace std;&const int N = 1000 + 5; struct Circle {&&&&int x, y, r;&&&&void read() {&&&&&&&&scanf("%d %d %d", &x, &y, &r);&&&&}}c[N];&double ans1, ans2;int n, vis[N];&bool can(Circle a, Circle b) {&&&&int dx = a.x - b.x;&&&&int dy = a.y - b.y;&&&&return dx*dx + dy*dy - (a.r + b.r)*(a.r + b.r) &= 0;}&bool dfs(int u) {&&&&vis[u] = 1;&&&&if(c[u].y - c[u].r &= 0)
return false;&&&&if(c[u].x - c[u].r &= 0)
ans1 = min(ans1, c[u].y - sqrt(c[u].r*c[u].r - c[u].x*c[u].x));&&&&if(1000 - c[u].x - c[u].r &= 0)
ans2 = min(ans2, c[u].y - sqrt(c[u].r*c[u].r - (1000 - c[u].x)*(1000 - c[u].x)));&&&&for(int i = 0; i & n; i++) {&&&& if(!vis[i]) {&&&&&&&& if (can(c[u], c[i]))&&&&&&&& if (!dfs(i))return false;&&&& } }&&&&return true;}&void solve() {&&&&ans1 = ans2 = 1000;&&&&for(int i = 0; i & n; i++) {&&&& if(!vis[i] && c[i].y + c[i].r&=1000) { &&&&&&&&if(!dfs(i)) { &&&&&&&&&&&&puts("IMPOSSIBLE"); &&&&&&&&&&&&return; &&&&&&&&} &&&&} }&&&&printf("0.00 %.2lf 1000.00 %.2lf\n", ans1, ans2);}&int main() {&&&&while (~scanf("%d", &n)) {&&&&&&&&memset(vis, 0, sizeof(vis));&&&&&&&&for(int i = 0; i & n; i++) {&&&&&&&& c[i].read();
}&&&&&&&&solve();&&&&}&&&&return 0;}
题目大意：有三种操作，CHANGE i v:将第i条边的权值改为v;NEGATE a b:将a,b结点路径上所有的边的权值取相反数;QUERY a b:求a,b结点路径上的最大的边权。
思路：首先是两个DFS将所有路径结点属性求出来，放到线段树上处理。线段树记录延迟标记、最大值、最小值，三个操作，一是单点更新；二是取相反数，这里是区间更新，将结点的最小值和最大值交换并分别取相反数，因为我们只求区间最大的边权，所以这样就可以得出取反后区间内最大的边权；三是区间查询。
#include &iostream&
#include &cstdio&
#include &cstring&
#include &algorithm&
#define lson rt && 1
#define rson rt && 1 | 1
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
int e[maxn][3];
int head[maxn],
int top[MAXN];//top[v]表示v所在的重链的顶端节点
int fa[MAXN]; //父亲节点
int deep[MAXN];//深度
int num[MAXN];//num[v]表示以v为根的子树的节点数
int p[MAXN];//p[v]表示v与其父亲节点的连边在线段树中的位置
int fp[MAXN];//和p数组相反
int son[MAXN];//重儿子
struct edgeType {
}edge[maxn && 1];
void addedge(int u, int v) {
edge[tot].to =
edge[tot].next = head[u];
head[u] = tot++;
//第一遍dfs求出fa,deep,num,son
void dfs(int u, int pre, int d) {
num[u] = 1;
for(int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].
if(v != pre) {
dfs(v, u, d + 1);
num[u] += num[v];
if(son[u] == -1 || num[v] & num[son[u]]) {
//第二遍dfs求出top和p
void getpos(int u, int sp) {
p[u] = pos++;
fp[p[u]] =
if(son[u] == -1)
getpos(son[u], sp);
for(int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].
if(v != son[u] && v != fa[u]) {
getpos(v, v);
struct node {
void opr() {
lazy ^= 1;
maxv *= -1;
minv *= -1;
swap(maxv, minv);
int mid() {
return (l + r) && 1;
}tree[maxn && 2];
void push_up(int rt) {
tree[rt].maxv = max(tree[lson].maxv, tree[rson].maxv);
tree[rt].minv = min(tree[lson].minv, tree[rson].minv);
void push_down(int rt) {
if(tree[rt].l == tree[rt].r) {
if(tree[rt].lazy) {
tree[lson].opr();
tree[rson].opr();
tree[rt].lazy = 0;
void build(int l, int r, int rt) {
tree[rt].l =
tree[rt].r =
tree[rt].maxv = 0;
tree[rt].minv = 0;
tree[rt].lazy = 0;
if(l == r) {
int m = tree[rt].mid();
build(l, m, lson);
build(m + 1, r, rson);
void update(int pos, int val, int rt) {
int l = tree[rt].l;
int r = tree[rt].r;
if(l == r) {
tree[rt].maxv = tree[rt].minv =
tree[rt].lazy = 0;
push_down(rt);
int m = tree[rt].mid();
if(pos &= m) update(pos, val, lson);
else update(pos, val, rson);
push_up(rt);
void toNegate(int s, int e, int rt) {
int l = tree[rt].l;
int r = tree[rt].r;
if(s &= l && r &= e) {
tree[rt].opr();
push_down(rt);
int m = tree[rt].mid();
if(s &= m) toNegate(s, e, lson);
if(e & m) toNegate(s, e, rson);
push_up(rt);
int query(int s, int e, int rt) {
int l = tree[rt].l;
int r = tree[rt].r;
if(s &= l && r &= e) {
return tree[rt].
push_down(rt);
int m = tree[rt].mid();
int mx = -
if(s &= m) mx = query(s, e, lson);
if(e & m) mx = max(mx, query(s, e, rson));
//查询u-&v边的最大值
int findMax(int u, int v) {
int f1 = top[u], f2 = top[v];
int tmp = -
while(f1 != f2) {
if(deep[f1] & deep[f2]) {
swap(f1, f2);
swap(u, v);
tmp = max(tmp,query(p[f1], p[u], 1));
u = fa[f1]; f1 = top[u];
if(u == v)
if(deep[u] & deep[v]) swap(u,v);
return max(tmp, query(p[son[u]], p[v], 1));
//把u-v路径上的边的值都设置为val
void Negate(int u, int v) {
int f1 = top[u], f2 = top[v];
while(f1 != f2) {
if(deep[f1] & deep[f2]) {
swap(f1, f2);
swap(u, v);
toNegate(p[f1], p[u], 1);
u = fa[f1]; f1 = top[u];
if(u == v)
if(deep[u] & deep[v]) swap(u, v);
return toNegate(p[son[u]], p[v], 1);
void init() {
memset(head, -1, sizeof head);
memset(son, -1, sizeof son);
int main() {
scanf("%d", &cases);
while(cases--) {
scanf("%d", &n);
for(int i = 0; i & n - 1; i++) {
scanf("%d %d %d", &e[i][0], &e[i][1], &e[i][2]);
addedge(e[i][0], e[i][1]);
addedge(e[i][1], e[i][0]);
dfs(1, 0, 0);
getpos(1, 1);
build(0, pos - 1, 1);
for(int i = 0; i & n - 1; i++) {
if(deep[e[i][0]] & deep[e[i][1]]) {
swap(e[i][0], e[i][1]);
update(p[e[i][1]], e[i][2], 1);
char op[10];
while(~scanf("%s", op)) {
if(op[0] == 'D') {
scanf("%d %d", &u, &v);
if(op[0] == 'Q') {
printf("%d\n", findMax(u, v));
else if(op[0] == 'N') {
Negate(u, v);
update(p[e[u - 1][1]], v, 1);
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236
#include &iostream&#include &cstdio&#include &cstring&#include &algorithm&using namespace std;&#define lson rt && 1#define rson rt && 1 | 1const int inf = 0x3f3f3f3f;const int maxn = 1e5 + 5;&int e[maxn][3];int head[maxn],tot;int top[MAXN];//top[v]表示v所在的重链的顶端节点int fa[MAXN]; //父亲节点int deep[MAXN];//深度int num[MAXN];//num[v]表示以v为根的子树的节点数int p[MAXN];//p[v]表示v与其父亲节点的连边在线段树中的位置int fp[MAXN];//和p数组相反int son[MAXN];//重儿子int pos;&struct edgeType { int to, next;}edge[maxn && 1];&void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;}&//第一遍dfs求出fa,deep,num,sonvoid dfs(int u, int pre, int d) { deep[u] = d; fa[u] = pre; num[u] = 1; for(int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if(v != pre) {
dfs(v, u, d + 1);
num[u] += num[v];
if(son[u] == -1 || num[v] & num[son[u]]) {
son[u] = v;
} }}&//第二遍dfs求出top和pvoid getpos(int u, int sp) { top[u] = sp; p[u] = pos++; fp[p[u]] = u; if(son[u] == -1) return ; getpos(son[u], sp); for(int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if(v != son[u] && v != fa[u]) {
getpos(v, v);
} }}&//线段树struct node { int l, r; int maxv, minv; int lazy; void opr() {
lazy ^= 1;
maxv *= -1;
minv *= -1;
swap(maxv, minv); } int mid() {
return (l + r) && 1; }}tree[maxn && 2];&void push_up(int rt) { tree[rt].maxv = max(tree[lson].maxv, tree[rson].maxv); tree[rt].minv = min(tree[lson].minv, tree[rson].minv);}&void push_down(int rt) { if(tree[rt].l == tree[rt].r) {
return; } if(tree[rt].lazy) {
tree[lson].opr();
tree[rson].opr();
tree[rt].lazy = 0; }}&void build(int l, int r, int rt) { tree[rt].l = l; tree[rt].r = r; tree[rt].maxv = 0; tree[rt].minv = 0; tree[rt].lazy = 0; if(l == r) {
return; } else {
int m = tree[rt].mid();
build(l, m, lson);
build(m + 1, r, rson); }}&void update(int pos, int val, int rt) { int l = tree[rt].l; int r = tree[rt].r; if(l == r) {
tree[rt].maxv = tree[rt].minv = val;
tree[rt].lazy = 0;
return; } push_down(rt); int m = tree[rt].mid(); if(pos &= m) update(pos, val, lson); else update(pos, val, rson); push_up(rt);}&void toNegate(int s, int e, int rt) { int l = tree[rt].l; int r = tree[rt].r; if(s &= l && r &= e) {
tree[rt].opr();
return; } push_down(rt); int m = tree[rt].mid(); if(s &= m) toNegate(s, e, lson); if(e & m) toNegate(s, e, rson); push_up(rt);}&int query(int s, int e, int rt) { int l = tree[rt].l; int r = tree[rt].r; if(s &= l && r &= e) {
return tree[rt].maxv; } push_down(rt); int m = tree[rt].mid(); int mx = -inf; if(s &= m) mx = query(s, e, lson); if(e & m) mx = max(mx, query(s, e, rson)); return mx;}&//查询u-&v边的最大值int findMax(int u, int v) {&&&&int f1 = top[u], f2 = top[v];&&&&int tmp = -inf;&&&&while(f1 != f2) {&&&&&&&&if(deep[f1] & deep[f2]) {&&&&&&&&&&&&swap(f1, f2);&&&&&&&&&&&&swap(u, v);&&&&&&&&}&&&&&&&&tmp = max(tmp,query(p[f1], p[u], 1));&&&&&&&&u = fa[f1]; f1 = top[u];&&&&}&&&&if(u == v) return tmp;&&&&if(deep[u] & deep[v]) swap(u,v);&&&&return max(tmp, query(p[son[u]], p[v], 1));}&//把u-v路径上的边的值都设置为valvoid Negate(int u, int v) {&&&&int f1 = top[u], f2 = top[v];&&&&while(f1 != f2) {&&&&&&&&if(deep[f1] & deep[f2]) {&&&&&&&&&&&&swap(f1, f2);&&&&&&&&&&&&swap(u, v);&&&&&&&&}&&&&&&&&toNegate(p[f1], p[u], 1);&&&&&&&&u = fa[f1]; f1 = top[u];&&&&}&&&&if(u == v)return;&&&&if(deep[u] & deep[v]) swap(u, v);&&&&return toNegate(p[son[u]], p[v], 1);}&void init() { tot = 0; pos = 0; memset(head, -1, sizeof head); memset(son, -1, sizeof son);}&int main() { int cases; scanf("%d", &cases); while(cases--) {
scanf("%d", &n);
for(int i = 0; i & n - 1; i++) {
scanf("%d %d %d", &e[i][0], &e[i][1], &e[i][2]);
addedge(e[i][0], e[i][1]);
addedge(e[i][1], e[i][0]);
dfs(1, 0, 0);
getpos(1, 1);
build(0, pos - 1, 1);
for(int i = 0; i & n - 1; i++) {
if(deep[e[i][0]] & deep[e[i][1]]) {
swap(e[i][0], e[i][1]);
update(p[e[i][1]], e[i][2], 1);
char op[10];
while(~scanf("%s", op)) {
if(op[0] == 'D') {
scanf("%d %d", &u, &v);
if(op[0] == 'Q') {
printf("%d\n", findMax(u, v));
else if(op[0] == 'N') {
Negate(u, v);
update(p[e[u - 1][1]], v, 1);
} } return 0;}