7/24·morning

问题 A: 铲雪车问题

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long x,y;
    long long a,b,c,d;
    double s;
    cin>>x>>y;
    while(cin>>a>>b>>c>>d){
        s+=sqrt((a-c)*(a-c)+(b-d)*(b-d));
    }
    s=s*2/20000;
    long long h=(long long)(s);
    long long m=s*60-h*60+0.5;
    printf("%lld:%02lld",h,m);
    return 0;
}

问题 B: 删边问题

#include<bits/stdc++.h>
using namespace std;

int main(){
    int m,n;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
    }
    cout<<m-n+1;
    return 0;
}

问题 C: 图的概念

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1005][1003];
int rd=0,cd=0,s=0;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            if(a[i][j]!=0)s++;
            if(i==m&&a[i][j]!=0)cd++;
            if(j==m&&a[i][j]!=0)rd++;
        }
    }
    cout<<m<<" "<<cd<<" "<<rd<<endl<<s<<endl;
    return 0;
}

问题 D: 边表邻接矩阵

#include<bits/stdc++.h>
using namespace std;
int n,m,a[103][103];
int rd=0,cd=0,s=0;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        a[u][v]=1;a[v][u]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

问题 E: 图的存储和遍历

#include<bits/stdc++.h>
using namespace std;
int n,vis[11];
int G[11][11];
vector<int> g[11];
void dfs(int x){
    cout<<x<<" ";
    vis[x]=1;
    for(int i=1;i<=g[x][0];i++){
        if(vis[g[x][i]]==0){
            dfs(g[x][i]);
        }
    }
}
void bfs(){
    memset(vis,0,sizeof(vis));
    queue<int> q;
    while(!q.empty())q.pop();
    q.push(1);
    vis[1]=1;
    while(!q.empty()){
        int h=q.front();q.pop();
        cout<<h<<" ";
        for(int i=1;i<=g[h][0];i++){
            if(vis[g[h][i]]==0){
                q.push(g[h][i]);
                vis[g[h][i]]=1;
            }
        } 
    }
} 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        g[i].push_back(0);
        for(int j=1;j<=n;j++){
            cin>>G[i][j];
            if(G[i][j]!=0){
                g[i][0]++;
                g[i].push_back(j);
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<i<<" ";
        for(int j=1;j<=g[i][0];j++){
            cout<<g[i][j]<<" ";
        }
        cout<<endl;
    }
    memset(vis,0,sizeof(vis));
    dfs(1);cout<<endl;
    bfs();
    return 0;
}

问题 B: 走出迷宫

#include<bits/stdc++.h>
using namespace std;
int n,m;int sx,sy,ex,ey;
char ch[103][103];
int vis[103][103];
int xx[4]={0,0,1,-1};
int yy[4]={1,-1,0,0};
struct node{
    int x,y;
};
void bfs(){
    queue<node> q;
    memset(vis,-1,sizeof(vis));
    while(!q.empty())q.pop();
    q.push({sx,sy});
    vis[sx][sy]=0;
    while(!q.empty()){
        node h=q.front();q.pop();
        //cout<<h.x<<" "<<h.y<<" "<<vis[h.x][h.y]<<endl; 
        for(int i=0;i<4;i++){
            int nx=h.x+xx[i];
            int ny=h.y+yy[i];
            if(nx>0&&nx<=n&&ny>0&&ny<=m&&vis[nx][ny]==-1&&ch[nx][ny]=='.'||ch[nx][ny]=='T'){
                q.push({nx,ny});
                vis[nx][ny]=vis[h.x][h.y]+1;
            }
            if(nx==ex&&ny==ey){
                cout<<vis[ex][ey]<<endl;
                return;
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ch[i][j];
            if(ch[i][j]=='S'){
                sx=i;sy=j;
            }
            if(ch[i][j]=='T'){
                ex=i;ey=j;
            }
        }
    }
    bfs();
    return 0;
}

问题 A: 资料发放

#include<bits/stdc++.h>
using namespace std;
int n,ans,vis[201];
vector<int> g[201];
void bfs(int st){
    queue<int> q;
    while(!q.empty())q.pop();
    q.push(st);
    vis[st]=1;
    while(!q.empty()){
        int h=q.front();q.pop();
        for(int i=1;i<=g[h][0];i++){
            if(vis[g[h][i]]==0){
                q.push(g[h][i]);
                vis[g[h][i]]=1;
            }
        } 
    }
} 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        g[i].push_back(0);
        int x;
        cin>>x;
        while(x!=0){
            g[i][0]++;
            g[i].push_back(x);
            cin>>x; 
        }
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            bfs(i);
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

 问题 D: 【提高】亲戚

#include<bits/stdc++.h>
using namespace std;
int n,m,p;
int fa[5001];
vector<int> g[5001];
int findfa(int x){
    if(fa[x]==x)return fa[x];
    else return findfa(fa[x]);
}
int main(){
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n;i++)g[i].push_back(0);
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u][0]++;g[v][0]++;
        g[u].push_back(v);
        g[v].push_back(u); 
    }
    for(int i=1;i<=p;i++){
        int a,b;
        cin>>a>>b;
        if(fa[a]==fa[b])cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}
/*未完成*/