T1 （T1.cpp/T1.in/T1.out）

给出一张N个点M条边的有向图，求从1出发能经过的最大点的编号为多少

N, M <= 100

输入

输入第一行两个数N,M

后面M行，每行一个x，y表示边的起点终点

输出一行为答案

Input

6 5

1 2

2 3

3 4

5 6

1 3

Output

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 1000using namespace std;bool vis[N];int n,m,x,y,tot,ans,head[N];struct Edge{    int from,to,next;}edge[N];int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}    while(ch<='9'&&ch>='0'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}int add(int x,int y){    tot++;    edge[tot].to=y;    edge[tot].next=head[x];    head[x]=tot;}int dfs(int x){    for(int i=head[x];i;i=edge[x].next)    {        int t=edge[i].to;        if(!vis[t])         vis[t]=1,ans=max(x,t),dfs(t);     }}int main(){    freopen("T1.in","r",stdin);    freopen("T1.out","w",stdout);    n=read();m=read();    for(int i=1;i<=m;i++)     x=read(),y=read(),add(x,y);    dfs(1);    printf("%d",ans);    return 0;}

T2（T2.cpp/T2.in/T2.out）

给出一个N个点M条边的无向图，每条边有一个权值。

请输出以q所在的连通块的权值总和

N, M <= 100

输入第一行三个数N,M,q

下面M行，每行一个x，y，z表示边的起点终点和权值

输出一行为答案

Input

5 3 3

1 2 3

5 3 5

3 4 2

Output

75分（没有环的情况）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 1000using namespace std;bool vis[N];int n,m,q,x,y,z,tot,ans,head[N];struct Edge{    int from,to,next,dis;}edge[N];int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}    while(ch<='9'&&ch>='0'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}int add(int x,int y,int z){    tot++;    edge[tot].to=y;    edge[tot].dis=z;    edge[tot].next=head[x];    head[x]=tot;}int dfs(int x){    vis[x]=true;    for(int i=head[x];i;i=edge[i].next)    {        int t=edge[i].to,sum=edge[i].dis;        if(!vis[t])         vis[t]=1,ans+=sum,dfs(t);     }}int main(){    freopen("T2.in","r",stdin);    freopen("T2.out","w",stdout);    n=read();m=read();q=read();    for(int i=1;i<=m;i++)     x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);    dfs(q);    printf("%d",ans);    return 0;}

AC代码：

这个题的第三个样例是有环的情况，我们如果还按上面的来写的话，就会出现少加了一条边。

所以，我们要换一种写法。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 1000using namespace std;bool vis[N];int n,m,q,x,y,z,tot,ans,head[N];struct Edge{    int from,to,next,dis;}edge[N];int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}    while(ch<='9'&&ch>='0'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}int add(int x,int y,int z){    tot++;    edge[tot].to=y;    edge[tot].dis=z;    edge[tot].next=head[x];    head[x]=tot;}void dfs(int x){    if(vis[x]) return ;    for(int i=head[x];i;i=edge[i].next)    {        int t=edge[i].to,sum=edge[i].dis;        vis[x]=1,ans+=sum,dfs(t);     }}int main(){    freopen("T2.in","r",stdin);    freopen("T2.out","w",stdout);    n=read();m=read();q=read();    for(int i=1;i<=m;i++)     x=read(),y=read(),z=read(),add(x,y,z),add(y,x,0);    dfs(q);    printf("%d",ans);    return 0;}