char buf[1000001],*p1=buf,*p2=buf;
#define get_char() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
#define R(a) do { \
  register char ch; \
  while((ch = get_char()) > '9' || ch < '0'); \
  for(a = ch-'0'; (ch = get_char()) >= '0' && ch <= '9'; a = a*10+ch-'0'); \
  }while(0)

此读入约比scanf快10倍;

原po主:5705317118


这一天小K到附近的山上去慢跑,这座山上有N个凉亭,简单地编号为1到N(山顶的凉亭编号为N,山底的凉亭编号为1)。有趣的是,如果凉亭i和凉亭j满足i 这些凉亭中存在一些道路,连接两个海拔不同的凉亭,穿过一条道路需要花一定的时间。但这里还有一个十分诡异的事件,这里存在一些特殊道路。从这些道路经过 小K可以回到过去,也就是说小K需要花的时间为负值。通过这些道路,小K可以花较短的时间跑完他需要跑的路程。这样他就可以节约下许多时间,回到机房刷水题。
小K想从凉亭1跑到凉亭N去,但他不想走下坡路,也就是说他想要走一条海拔递增的路径,因为 小K始终认为递增的东西是具有美感的。
小K他想知道他最少需要花多少时间就可以从山底的凉亭到达山顶的凉亭?有一点需要注意,小K到达山顶的凉亭的时间可能会小于他出发的时间, 这就意味着他穿越了时空。这是一件多么美妙的事,于是 小K也想知道他是否能穿越时空。
他把这个任务交给了你,他希望你能告诉他最少需要花多少时间才能到达山顶,同时你也需要告诉他,他是否能穿越时空。


输入数据第一行包含三个整数N,ML,MD(分别用一个空格隔开),分别表示凉亭的数目,普通道路的数目和特殊道路的数目;
第2行到第ML+1行,每行三个整数Ai,Bi,Ci(分别用一个空格隔开,1≤Ai,Bi≤N,Ai≠Bi),表示普通道路连接凉亭Ai和Bi,穿过这条道路需要花时间Ci;
第ML+2行到第ML+MD+1行,每行三个整数Ai,Bi,Ci(分别用一个空格隔开,1≤Ai,Bi≤N,Ai≠Bi),表示特殊道路连接凉亭Ai和Bi,穿过这条道路会回到相对时间Ci之前。

输出数据包含两行。
第一行包含一个整数T,表示小K最少花多少时间能到达山顶的凉亭;
第二行包含一个字符串“YES”或“NO”(不包含引号),如果小K可以回到过去那么输出“YES”,否则输出“NO”。

 

很明显,应该使用最短路算法,因为有负权,故选用spfa,所谓的海拔升序不需特意排序,只需在建图时对凉亭序号进行比较再建图即可;
AC代码:

#include<iostream>
#include<stdio.h>
#include<queue>
#define N 1000005
#define oo 0x7fffffff/2
using namespace std;
int h[N],dis[N],used[N],vis[N];
int n,ml,md,cnt;
struct edge
{
    int to,next,v;
}a[N];
void add(int x,int y,int z)
{
    a[++cnt].next=h[x];
    a[cnt].to=y;
    a[cnt].v=z;
    h[x]=cnt;
}
queue<int> q;
int u,v;
void spfa()
{
    for(int i=1;i<=n;i++)dis[i]=oo;
    q.push(1);
    dis[1]=0;
    vis[1]=1;
    used[1]++;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=h[u];i;i=a[i].next)
        {
            v=a[i].to;
            if(dis[v]>dis[u]+a[i].v)
            {
                dis[v]=dis[u]+a[i].v;
                if(!vis[v])
                {
                    used[v]++;
                    if(used[v]==n)return ;
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&ml,&md);
    for(int i=1;i<=ml;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(x<y)add(x,y,z);
        else add(y,x,z);
    }
    for(int i=1;i<=md;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(x<y)add(x,y,-z);
        else add(y,x,-z);
    }
    spfa();
    printf("%d\n",dis[n]);
    if(dis[n]<0)puts("YES");
    else puts("NO");
    return 0;
   
   
}

今天看到一篇文章,似乎传播甚广,大概看了一下,槽点太多,随意写一点:

在文章之首,我们可以看到这样一句话

不久之前,美国一位心理学家公布了自己长达十年的研究结果,令人震惊。

标准的震惊体,但是有几个关键词值得我们注意:美国/心理学家/长达十年/震惊;

接下来我们便立足于这几个词对其进行反驳。

首先看到这段话:

这位科学家在10年前从全国各地的中下阶层的家庭中选取了100名孩子,将他们分成了两组:50名是接触不到手机的孩子,50名是对手机痴迷的孩子。然后对他们进行跟踪调查。

这篇文章发布于2018年7月28日,我们姑且认定这篇文章是作者原创,那么10年前便是2008年;

2008年的美国经济是怎么一个状况呢?我随手在百度上搜索了一下:

 

众所周知,2008是金融危机的一年;那么文章中的中下阶层又是指什么呢?

查了很久,只找到一篇2010年的关于美国阶层介绍的文章,年代相差不大,仅作参考:

我们简单的分为前50%和后50%,而中下阶层,无疑是从50%往后的那一部分,即文章中的“劳动阶层”;

劳动阶层包括中等收人的蓝领工人和那些过着“劳动阶层生活方式”的人,而不论他们的收人多高、学校背景及职业怎样。劳动阶层主要依靠亲朋好友在经济上和道义上的援助,依靠他们介绍就业机会,购物听从他们的忠告,困难时期依靠他们的帮助。度假对于劳动阶层来说,指的是“呆在城里”, “外出”指的是到湖边去,或常去不到两小时远的地方。劳动阶层仍然保持着明显的性别分工和陈旧习惯,他们偏好的汽车包括标准型号或较大型号的汽车,对国内外的小型汽车并不问津。

简单的说,就是收入刚好补贴家用的那一批人,在10年前,这部分人真的会舍得给孩子一部“智能手机”吗?

我们姑且认为这位“美国心理学家”找到的家庭都宁愿攒钱也要给孩子一部手机,那我们再来看看10年前的手机市场:

看到了吧,诺基亚是当之无愧的老大哥,而后来的巨头Apple占比仅2.1%;

那时的手机长什么样子呢?

诺基亚1209

诺基亚2600c

当然,也有真正的智能手机,比如下面这个:

 

诺基亚N96

但是它的首发售价820美元,这是什么概念呢?按照2008年中美汇率平均6.9来算就是5658人民币;

通过查询2008年的世界人均年收入(链接:/wenku.baidu.com/view/2d5bf43eee06eff9aef807a3.html)我们可以算出当时的美国人月均收入在3000美元左右,大约等于3.6部这样的手机,而他的目标定位是商务人士,能在2008年得到这部手机的“孩子”绝对是凤毛麟角,也决不可能是所谓的“中下阶层”的孩子;

而例子中的前两部手机已经不属于“智能手机”,也就无需讨论了;

所以我们便可以很轻松的推翻这篇文章的中心论点:

可见,毁掉一个孩子的最好办法就是给他一部手机!

但是!

肯定有人会说,这只是一篇鸡汤文,前面怎么瞎扯不重要,关键是后面的要点啊!

那么我们也可以一个个进行分析:

首先:

智能手机影响儿童健康

智能手机伤害孩子视力,导致孩子失明或者伤害孩子颈椎,导致孩子颈椎变形的新闻屡见不鲜。

孩子临睡前玩手机,手机画面过于明亮,会影响人体褪黑素的分泌,导致睡眠障碍。

沉迷智能手机的孩子常常会对运动锻炼表现出消极态度,导致运动能力低下,进而影响孩子的生长发育。

这便是这类文章的典型手法:偷换概念;

化学界流传这样一句话:离开剂量谈毒性,都是耍流氓。

这句话虽然有些调侃意味,在某些情境下也或许不够严谨,但在这里却是再适合不过。

在2018年,智能手机已经是必备的生活用品,这句话看数据更加直观:

可以看到,中国手机持有量已接近100%,而智能手机持有量也大约在70%,也就是超过9.6亿人都有智能手机,而其中真正身体健康受到损害的又有几何?其真实性不言而喻。

其次:

手机让孩子患上抑郁症

有专家表示,花费在手机上的时间越多,越喜欢宅在家里的人,患上抑郁症的几率就越高,经常玩手机的孩子患抑郁症的比例远高于一般孩子。

这是因为智能手机能够快速便捷地让孩子得到满足感,缩短注意力持续时间,让人越来越感到厌倦,所以过度使用手机会让人容易抑郁。

能写出这样不负责任的文字,其作者的知识水平便可见一斑了,其实这也是这类文章的一个标准手法:借助一些人们谈之色变的可怕后果增加人们对文章的信任,毕竟绝大多数人都抱着一种宁可信其有不可信其无的观念,殊不知有时却因此受人误导。

我们先不管这个及其老套的”专家表示“,我们就事论事说一下抑郁症和手机的关系:

我在这里引用一篇文章,文中的研究与专家皆是有名有姓,可信度应该较高;

其中指出了

抑郁症其实是一种代谢性疾病

也提到了代谢性抑郁症的其中一个病因:多巴胺少;

然而讽刺的是,原文中又有这样一句话:

这是因为智能手机能够快速便捷地让孩子得到满足感,缩短注意力持续时间,让人越来越感到厌倦,所以过度使用手机会让人容易抑郁。

提到满足感,略有常识的人都应该想到作者在指多巴胺,所以这个观点也是不攻自破;

然后:

手机损伤脑神经 

孩子的生理构造和生理形态与成人不同,手机、平板电脑等无线电设备产生的电磁波辐射对儿童神经系统的伤害远大于成人,过度接触电磁波辐射对儿童健康状况和认知力会产生一定影响。

这就真的纯属瞎扯了,任何一个人无时无刻不处在大量电磁波中,如果真的要提手机的辐射量,它的辐射量还不如路由器高,而这类谣言也早有人出面澄清过,生活中的电磁波辐射是对人体无害的;

最后:

手机耽误孩子学习

喜欢玩手机的孩子,习惯了手机带来的轻松愉悦的信息,对知识学习感到枯燥乏味,学习成绩下降,受到指责后更需要在手机网络里找到慰藉,形成恶性循环之后,孩子逐渐丧失求知欲,产生厌学情绪。

手机可以方便快捷地寻找习题答案,很多学生面对难题不再查找书本,深入思考,完全依靠手机搜索答案,导致了孩子产生思维惰性。

考试没有答案可查,一个不喜欢思考的学生是不会有好成绩的。

每个孩子的时间都是一样多的,精力也是如此,整天沉迷于手机世界里,花费在学习上的时间、精力自然就少了,久而久之,学习成绩必然下滑。

这便是这类文章的另一个标准手法:迎合读者;

某些能力低的父母或学生将一切原因归咎在手机上,却忽视了从自己身上找问题的重要性;而赞同这类文章的人一般都有此类问题,找一个借口掩盖自己的不足恰好迎合了这类读者思考问题的方式,也更让本就赞同它的人对此深信不疑;

实际上这个问题也是见仁见智,从课外书到网络,再到如今的手机,关于这类“双刃剑”的争论就从未停止,每个人心中都有自己的答案,我不能全盘否定,也不说赞同。

最后,这类文章能火起来依靠的就是那些不善于思考并且对于流言缺乏基本辨识能力的人,这样的人面对“双刃剑”这样的问题也只会随从大流而缺乏自己的思考。本文只作随笔,挂在博客上也能警示自己要懂得独立思考,磨砺思想。

 

 


【题目背景】
在一个热带雨林中生存着一群猴子,它们以树上的果子为生。昨天下了一场大雨,现在雨过天晴,但整个雨林的地表还是被大水淹没着,部分植物的树冠露在水面上。猴子不会游泳,但跳跃能力比较强,它们仍然可以在露出水面的不同树冠上来回穿梭,以找到喜欢吃的果实。
现在,在这个地区露出水面的有N棵树,假设每棵树本身的直径都很小,可以忽略不计。我们在这块区域上建立直角坐标系,则每一棵树的位置由其所对应的坐标表示(任意两棵树的坐标都不相同)。
在这个地区住着的猴子有M个,下雨时,它们都躲到了茂密高大的树冠中,没有被大水冲走。由于各个猴子的年龄不同、身体素质不同,它们跳跃的能力不同。有的猴子跳跃的距离比较远(当然也可以跳到较近的树上),而有些猴子跳跃的距离就比较近。这些猴子非常聪明,它们通过目测就可以准确地判断出自己能否跳到对面的树上。
【问题描述】
现已知猴子的数量及每一个猴子的最大跳跃距离,还知道露出水面的每一棵树的坐标,你的任务是统计有多少个猴子可以在这个地区露出水面的所有树冠上觅食。

第1行为一个整数,表示猴子的个数M(2<=M<=500);
第2行为M个整数,依次表示猴子的最大跳跃距离(每个整数值在1–1000之间);
第3行为一个整数表示树的总棵数N(2<=N<=1000);
第4行至第N+3行为N棵树的坐标(横纵坐标均为整数,范围为:-1000–1000)。
(同一行的整数间用空格分开)

输出文件monkey.out包括一个整数,表示可以在这个地区的所有树冠上觅食的猴子数。

读题之后可以将题目进行转换——以树的坐标建图,以欧几里德距离为边权,求出最小生成树的权和,即是猴子们要到达每个点所需的最小距离和;

AC代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define M 1005
#define N 1000005
using namespace std;
int prt[N],x[M],y[M],j[M];
int n,m,ans,cnt,fx,fy;
double q;
struct point{int x,y,z;}a[N];
int cmp(point a,point b){return a.z<b.z;}
int find(int x)
{
    if(prt[x]==x)return x;
    else return prt[x]=find(prt[x]);
}
void init()
{
    scanf("%d",&m);
    for(int i=1;i<=m;i++)cin>>j[i];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        prt[i]=i;
        scanf("%d%d",&x[i],&y[i]);
    }  
}
void getdis()
{
        for(int i=1;i<=n;i++)
        {
            int xx=x[i];
            int yy=y[i];
            for(int j=1;j<i;j++)
            {
                int s=(xx-x[j])*(xx-x[j])+(yy-y[j])*(yy-y[j]);
                a[++cnt].x=i;
                a[cnt].y=j;
                a[cnt].z=s;
            }
        }
}
double kruskal()
{
    for(int i=1;i<=cnt;i++)
    {
        int x=find(a[i].x);
        int y=find(a[i].y);
        if(x!=y)
        {
            prt[x]=y;
            ans=a[i].z;
        }  
    }
    return sqrt(ans);
}
int main()
{
    / freopen("monkey.in","r",stdin);
    / freopen("monkey.out","w",stdout);
    init();
    getdis();
    sort(a+1,a+1+cnt,cmp);
    q=kruskal();
    ans=0;
    for(int i=1;i<=m;i++)if(q<=j[i])ans++; 
    printf("%d",ans);
    return  0;
}


hyc碰到了一个难题,请你来帮忙解决。

对于不定方程a1+a2+…+ak-1+ak=g(x),其中k≥2且k∈N,x是正整数,g(x)=x^x mod 1000(即x^x除以1000的余数),x,k是给定的数。我们要求的是这个不定方程的正整数解组数。

举例来说,当k=3,x=2时,分别为(a1,a2,a3)=(2,1,1)'(1,2,1),(1,1,2)。

输入文件equation.in有且只有一行.为用空格隔开的两个正整数,依次为k,x.

输出文件equation.out有且只有一行,为方程的正整数解组数.

 

裸的数论可重组合;

但是看到数据范围我们知道需要快速幂与高精度运算;

这里直接把高精度写到组合里;

AC代码:

#include<cstdio>
#include<iostream>
int k,x,c[1005]={1,1};
using namespace std;
int ksm(int a,int c)
{
    int ans=1;
    int b=a;
    while(b)
    {
        if(b&1){ans=(ans*a)%c;}
        a=a*a%c,b>>=1;
    }
    return ans;
}
void print(int c[])
{
    cout<<c[c[0]];
    for(int i=c[0]-1;i>=1;i--)cout<<c[i]/1000<<c[i]/100%10<<c[i]/10%10<<c[i]%10;
    return;
}
void solve(int a,int b)
{
    for(int k=1;k<=b;k++)
    {
        int p=c[0];
        for(int i=1;i<=p;i++)c[i]*=a-k+1;
        for(int i=1;i<=p;i++)
        {
            c[i+1]+=c[i]/10000;
            c[i]%=10000;
        }
        while(c[c[0]+1]){c[0]++;}
        int y=0;
        for(int i=c[0];i>=1;i--)
        {
            y=y*10000+c[i];
            c[i]=y/k,y%=k;
        }
        while(!c[c[0]])c[0]--;
    }
}
int main()
{
    cin>>k>>x;
    x%=1000;
    x=ksm(x,1000)-1;
    k--;
    solve(x,k);
    print(c);
}

一个数x可以按以下规则生成数字:
1、将任意两位交换,若交换的数字为a和b,生成的代价为((a and b)+(a xor b))2。
例如134可以生成431,因为431可以从134的个位(4)与百位(1)交换后得到,代价为((1 and 4)+(1 xor 4))
2=10。
2、将其中一位数删除,但是删除的数要满足大等于它左边的数,且小等于它右边的数,并且定义最高位左边的数为个位,个位右边的数为最高位。若删除的数字为a,它左边的数为b,它右边的数为c,则生成的代价为a+(b and c)+(b xor c)。
例如212,可以删除个位的数得到21,但是因为2>1,所以1是不能被删除的。特别地,若x为两位数,它能删除当且仅当x的两位数相同,若x为一位数,它是不能被删除的。
3、在两位数字之间,也可以是数字的前面或后面加入一位数,同样地,加入的数要满足大等于它左边的数,且小等于它右边的数,并且定义最高位左边的数为个位,个位右边的数为最高位。若加入的数字为a,它左边的数为b,它右边的数为c,则生成的代价为a+(b and c)+(b xor c)。
例如241,它可以在2与4之间加入一个3,生成2341,也可以在数的末尾加入一个1或者2,当然还有其它可以生成的数,但是不能在4和1之间加入数字。
你的任务是,S一开始为n个不同的给定数组成的集合,每次可以从S中取出一个数生成一个满足生成规则的数加入S中,并且取出的数仍然存在于S中。生成的数的位数不能大于S初始集合最大的数的位数。问在S元素最多的情况下,总代价最小是多少。

输入的第1行为一个正整数n,为集合S初始元素个数。
第2行包含n个正整数a1,a2, …, an,数之间空格隔开,为S中初始元素。

输出包括一个正整数,为最小代价。

【数据规模】
对于20%的数据,有ai<100;
对于40%的数据,有ai<1000;
对于50%的数据,有n=1;
对于60%的数据,有ai<10000;
对于100%的数据,有ai<100000,n≤5,保证的任何一位不包含0。

依靠BFS生成数字并求出最小生成树;

AC代码(真的难写):

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#define LL longlong
#define FOUP(a,b,s) for(int s=a;s<=b;s++)
#define FDOW(a,b,s) for(int s=a;s>=b;s++)
#define R(a) scanf("%d",&a)
#define RV scanf("%d%d%d",&x,&y,&z);
#define WI(a) printf("%d\n",a)
#define WLL(a) printf("%lld ",a)
#define INF 0x7fffffff/2
#define M 1005
#define N 100005
using namespace std;
int cnt,ans,maxn,maxl,l=1,r,n;
int h[N],vis[N],q[N],num[15],num0,fa[N];
struct edge
{
    int a,b,v;
}w[N*100];
bool cmp(edge a,edge b)
{
    return a.v<b.v;
}
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void add(int a,int b,int v)
{
    w[++cnt].a=a;w[cnt].b=b;w[cnt].v=v;
}
int number(int a[],int a0)
{
    int sum=0;
    for(int i=a0;i;i--)sum=sum*10+a[i];
    return sum;
}
void init()
{
    R(n);
    for(int i=1;i<=n;i++)
    {
        int x;
        R(x);
        q[++r]=x;
        vis[x]=1;
        maxn=max(maxn,x);
    }
    FOUP(1,n-1,i)add(q[i],q[i+1],0);
    maxl=int(log10(maxn))+1;
    maxn=1;
    FOUP(1,maxl,i)maxn*=10;
}
int calc1(int a,int b)
{  
    return ((a&b)+(a^b))*2;
}
int calc2(int a,int b,int c)
{
    return a+(b&c)+(b^c);
}
void get1(int num[],int num0)
{
    int a=number(num,num0);
    FOUP(1,num0-1,i)
        FOUP(i+1,num0,j)
        if(num[i]!=num[j])
        {
            swap(num[i],num[j]);
            int to=number(num,num0);
            int f=calc1(num[i],num[j]);
            add(a,to,f);
            add(to,a,f);
            swap(num[i],num[j]);
            if(!vis[to])
            {
                q[++r]=to;
                vis[to]=1; 
            }  
        }
}
void get2(int num[],int num0)
{
    if(num0==1)return;
    int tp[15]={0},tp0;
    int a=number(num,num0);
    FOUP(1,num0,i)
    {
        if(num[i]<=num[i-1]&&num[i]>=num[i+1])
        {
            for(int j=1;j<i;j++)tp[j]=num[j];
            for(int j=i;j<=num0;j++)tp[j]=num[j+1];
            tp0=num0-1;
            int to=number(tp,tp0);
            int f=calc2(num[i],num[i-1],num[i+1]);
            add(a,to,f);
            add(to,a,f);
            if(!vis[to])
            {
                q[++r]=to;
                vis[to]=1;
            }
        }
    }
}
void get3(int num[],int num0)
{
    if(num0==maxl)return;
    int tp[15]={0},tp0;
    int a=number(num,num0);
    FOUP(1,num0+1,i)
    {
        if(num[i]<=num[i-1])
        {
            for(int j=num0+1;j>i;j--)tp[j]=num[j-1];
            for(int j=1;j<i;j++)tp[j]=num[j];
            tp0=num0+1;
            FOUP(num[i],num[i-1],j)
            {
                tp[i]=j;
                int to=number(tp,tp0);
                int f=calc2(j,num[i],num[i-1]);
                add(a,to,f);
                add(to,a,f);
                if(!vis[to])
                {
                    q[++r]=to;
                    vis[to]=1;
                }
            }
           
        }
    }
}
void kruskal()
{
    FOUP(1,maxn,i)fa[i]=i;
    sort(w+1,w+cnt+1,cmp);
    FOUP(1,cnt,i)
    {
        int f1=find(w[i].a);
        int f2=find(w[i].b);
        if(f1!=f2)
        {
            ans+=w[i].v;
            fa[f1]=f2;
        }
    }
}
void solve()
{
    int num0;
    while(l<=r)
    {
        int a=q[l];
        num0=0;
        memset(num,0,sizeof(num));
        while(a)
        {
            num[++num0]=a%10;
            a/=10;
        }
        num[0]=num[num0];
        num[num0+1]=num[1];
        get1(num,num0);
        get2(num,num0);
        get3(num,num0);
        l++;
    }
    kruskal();
    WI(ans);
}
int main()
{
    init();
    solve();
    return 0;
}

某军搞信息对抗实战演习.红军成功地侵入了蓝军的内部网络.蓝军共有两个信息中心.红军计划在某台中间服务器上安装一个嗅探器,从而能够侦听到两个信息中心互相交换的所有信息.但是蓝军的网络相当的庞大,数据包从一个信息中心传到另一个信息中心可以不止有一条通路.现在需要你尽快地解决这个问题.应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获?

输入文件的第一行一个整数n(1<=n<=100),表示蓝军网络中服务器的数目. 接下来若干行是对蓝军网络的拓扑结构描述. 每行是两个整数i,j表示编号为I和编号为j的两台服务器间存在连接(显然连接是双向的).服务器的编号从1开始.描述一两个0结束. 再接下来一行是两个整数a,b分别表示两个中心服务器的编号.

输出编号。如果有多个解输出编号最小的一个.如果找不到任何解,输出”No solution”.

通过tarjan求出割点再判断一下

#include<bits/stdc++.h>
using namespace std;
#define N 1001
#define MAXN  0x7fffffff
int n,p,r,a,b,root,cnt,cot,ans=MAXN;
int first[N],dfn[N],low[N],pri[N];
struct node/使用邻接表进行存图
{
    int u,v;
    int nxt;
}e[N*100];
void add(int u,int v)/建图
{
    e[++cnt].nxt=first[u];
    first[u]=cnt;
    e[cnt].u=u;
    e[cnt].v=v;
}
void dfs(int u,int fa)/tarjan求解割点
{
    int son=0;
    dfn[u]=low[u]=++cot;
    for(int i=first[u];i;i=e[i].nxt)/邻接表循环
    {
        int v=e[i].v;/ 通向的点
        if(dfn[v]==0)/未被访问
        {
            pri[v]=u;/设置u父亲为v
            dfs(v,u);/dfs
            low[u]=min(low[u],low[v]);/对low[]进行维护
        }
        else
            if(v!=fa)/访问过且不是回环
                low[u]=min(low[u],dfn[v]); 
    }  
}
 
void init()/初始化
{
    cnt=0;cot=0;int x,y;
    memset(first,0,sizeof(first));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(pri,0,sizeof(pri));
    cin>>n;
    while(cin>>x>>y)/读入若干行
    {
        if(x==0&&y==0)break;
        add(x,y);add(y,x);
    }
    cin>>a>>b;
}
void check(int t)/递归验证答案
{
    if(t==root) return;/找到的点是自己则return
    if(low[t]>=dfn[pri[t]]&&pri[t]!=root&&pri[t]<ans)
    ans=pri[t];
    check(pri[t]);
    /*low[t]>=dfn[pri[t]]:第一次递归时t=b,向上递归,因为定理2若成立即为割点
    pri[t]!=root:确认找到的点不是a;
    pri[t]<ans:即ans=min(pri[t],ans);
    */

}
 
int main()
{  
    init();
    root=a;
    dfs(root,-1);
    check(b);  
    if(ans<MAXN)/找答案
        printf("%d",ans);
    else
        printf("No solution");
    return 0;
}

A Telephone Line Company (TLC) is establishing a new telephone cable network. They are connecting several places numbered by integers from 1 to N . No two places have the same number. The lines are bidirectional and always connect together two places and in each place the lines end in a telephone exchange. There is one telephone exchange in each place. From each place it is
possible to reach through lines every other place, however it need not be a direct connection, it can go through several exchanges. From time to time the power supply fails at a place and then the exchange does not operate. The officials from TLC realized that in such a case it can happen that besides the fact that the place with the failure is unreachable, this can also cause that some other places cannot connect to each other. In such a case we will say the place (where the failure
occured) is critical. Now the officials are trying to write a program for finding the number of all such critical places. Help them.

给你一个无向图,有n个节点,编号从1到n,若干条边,现在要你求出求其中的割点个数。

The input file consists of several blocks of lines. Each block describes one network. In the first line of each block there is the number of places N < 100. Each of the next at most N lines contains the number of a place followed by the numbers of some places to which there is a direct line from this place. These at most N lines completely describe the network, i.e., each direct connection of two places in the network is contained at least in one row. All numbers in one line are separated
by one space. Each block ends with a line containing just 0. The last block has only one line with N = 0;

输入文件包含多组测试数据,每组数据的第一行为一个整数n(n<=100),表示节点个数,接下来最多n行,每行的第一个数字表示节点,接下来的若干个数字表示该节点所连接的节点编号。每组数据以一个0为一行作为结束。文件也以一个0为一行作为结束。

The output contains for each block except the last in the input file one line containing the number of critical places.

每组数据输出一行为该无向图的割点个数。

求割点模版题,使用tarjan求解割点,当为根或为割点时ans++,注意输入的处理。
AC代码:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int dfn[105],low[105],prt[105],g[105][105];
int n,cnt,ans,son,vis[105];
void init()
{  int i,j; char ch;
   cnt=0,ans=0;son=0;
   memset(prt,0,sizeof(prt));
   memset(g,0,sizeof(g));
   memset(dfn,0,sizeof(dfn));
   memset(vis,0,sizeof(vis));
   while(scanf("%d",&i)&&i!=0)
   {  
        while(1)
        {    
            scanf("%d%c",&j,&ch);
            g[i][j]=1;g[j][i]=1;
            if(ch=='\n')break;
        }
   }
}
void dfs(int u)
{  int i;
   low[u]=dfn[u]=++cnt;
   for(int i=1;i<=n;i++)
      if(g[u][i]&&prt[u]!=i)
        {  if(!dfn[i])
            {  
                prt[i]=u;
                dfs(i);
                low[u]=min(low[u],low[i]);
                if(low[i]>=dfn[u])
                {
                    if(!vis[u]){ans++;vis[u]=1;}
                    if(u==1)son++;
                }
            }
            else low[u]=min(low[u],dfn[i]);
        }
}
int main()
{  
    while(scanf("%d",&n))
    {  
        if(n==0)break;
        init();
        dfs(1);
        if(son==1)ans--;
        printf("%d\n",ans);
   }
}


对于完全图 G, 若有且仅有一棵最小生成树为 T ,则称完全图 G 是树 T 的扩展出的。
给你一棵树 T, 找出 T 能扩展出的边权和最小的完全图 G 。

第一行 N 表示树 T 的点数。
接下来 N-1 行: Si , Ti , Di ;描述一条边( Si,Ti )权值为 Di 。
保证输入数据构成一棵树。

一个数,表示最小的图 G 的边权和。

#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1000005
using namespace std;
int n,m,p[N],k=0,s[N];
long long ans=0;
struct node{int p,x,y,z;}a[N];
int cmp(node a,node b){return a.z<b.z;}
int find(int x){return p[x]==x?x:p[x]=find(p[x]);}
void kt(){
    for(int i=1;i<=n-1;i++)
    {
        int f1=find(a[i].x);
        int f2=find(a[i].y);
        if(f1!=f2)
        {
            ans=ans+(long long)(a[i].z+1)*(s[f1]*s[f2]-1)+a[i].z;
            p[f1]=f2;
            s[f2]+=s[f1];
        }
    }
    cout<<ans;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){p[i]=i;s[i]=1;}
    for(int i=1;i<=n-1;i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].z;
    }
    sort(a+1,a+n,cmp);
    kt();
    return 0;
}