头像

13751721187


访客:170

在线 



13751721187
6小时前
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=100010;
int n1,n2,m,h[N],ne[M],e[M],idx;
bool st[N];
int match[N];

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}


int find(int x){
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]){
            st[j]=true;
            if(!match[j]||find(match[j])){
                match[j]=x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    memset(h,-1,sizeof(h));
    scanf("%d%d%d",&n1,&n2,&m);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    int res=0;
    for(int i=1;i<=n1;i++){
        memset(st,false,sizeof(st));
        if(find(i)) res++;
    }  
    printf("%d",res);
}



13751721187
8小时前
#include<bits/stdc++.h>

using namespace std;
const int N=1e5+10,M=2e5+10;
int e[M],ne[M],h[N],idx,st[N];

void add(int a, int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool dfs(int u,int color) {
    st[u]=color;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]){
            if(!dfs(j,3-color)) return false;
        }
        else if(st[j]==color){
            return false;
        }
    }

    return true;
}

int main(){
    int n,m;
    scanf("%d%d", &n,&m);
    memset(h,-1,sizeof(h));
    while (m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }

    bool flag=true;
    for(int i=1;i<=n;i++){
        if(!st[i]){
            if(!dfs(i,1)){
                flag=false;
                break;
            }
        }
    }

    if(flag) printf("Yes");
    else printf("No");
    return 0;
}



13751721187
8小时前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e5+10,INF=0x3f3f3f3f;
int n, m,p[N];
struct Edge{
    int u,v,w;
    bool operator<(const Edge&T)const{
        return w<T.w;
    }
}edges[M];

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int kruskal(){
    sort(edges,edges+m);
    for(int i=1;i<=n;i++) p[i]=i;
    int res=0,cnt=0;
    for(int i=0;i<m;i++){
        auto t=edges[i];
        t.u=find(t.u),t.v=find(t.v);
        if(t.u!=t.v){
            p[t.u]=t.v;
            res+=t.w;
            cnt++;
        }
    }

    if(cnt<n-1) return INF;
    return res;
}

int main() {
    scanf("%d%d",&n,&m);
    int u, v, w;
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&u,&v,&w);
        edges[i]={u,v,w};
    }
    int x=kruskal();
    if(x>INF/2) printf("impossible");
    else printf("%d",x);
}



13751721187
12小时前
#include<bits/stdc++.h>
using namespace std;
const int N=510,INF=0x3f3f3f3f;

int n,m,g[N][N],dist[N];
bool st[N];

int prim(){
    memset(dist,INF,sizeof(dist));
    int res=0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++) if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; 
        if(i&&dist[t]==INF) return INF;
        if(i) res+=dist[t];
        st[t]=true;
        for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);
    }

    return res;
}

int main() {
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) g[i][j]=0;
            else g[i][j]=INF;
        }
    }
    while(m--){
        scanf("%d%d%d",&u,&v,&w);
        g[u][v]=g[v][u]=min(g[u][v],w);
    }
    int t=prim();
    if(t==INF) printf("impossible");
    else printf("%d",t);
}


活动打卡代码 AcWing 854. Floyd求最短路

13751721187
16小时前
#include<bits/stdc++.h>
using namespace std;
const int N=210,M=2e+10,INF=1e9;
int n,m,k,x,y,z,d[N][N];

void floyd(){
    for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) d[i][j]=0;
            else d[i][j]=INF;
        }
    }
    while(m--){
        scanf("%d%d%d",&x,&y,&z);
        d[x][y]=min(d[x][y],z);
    }
    floyd();
    while(k--){
        scanf("%d%d",&x,&y);
        if(d[x][y]>INF/2) printf("impossible\n");
        else printf("%d\n",d[x][y]);
    }
}


活动打卡代码 AcWing 852. spfa判断负环

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
const int Inf = 0x3f3f3f;
int head[N],vis[N],dis[N],net[N],to[N],ata[N],idx=1,sum[N],n,m;
void add(int x,int y,int z){
    ata[idx]=z;
    to[idx]=y;
    net[idx]=head[x];
    head[x]=idx++;
}
bool spfa(){
    bool flag=0;
    queue<int>p;
    for(int i=1;i<=n;i++){
        p.push(i);
        dis[i]=0;
        vis[i]=i;
        sum[i]++;   
    }
    while(!p.empty()){   
        int t=p.front();
        vis[t]=0;
        p.pop();
        for(int i=head[t];i;i=net[i]){
            int j=to[i];
            if(dis[j]>dis[t]+ata[i]){
                dis[j]=dis[t]+ata[i];
                if(!vis[j]){
                    vis[j]=1;
                    p.push(j);
                    if(j==n) flag=1;
                    sum[j]++;
                    if(sum[j]>n) return false;
                }
            }
        }
    }
    return true;
}
int main(){
    memset(dis,Inf , sizeof(dis));
    scanf("%d%d",&n,&m);
    while(m--){
        int x, y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    if(!spfa())printf("Yes\n");
    else printf("No");
}


活动打卡代码 AcWing 851. spfa求最短路

#include<bits/stdc++.h>

using namespace std;
const int N=100010;
int h[N],e[N],ne[N],idx,w[N],dist[N],n,m;
bool st[N];
void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;

}
int spfa(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    queue<int>q;
    q.push(1);
    st[1]=true;
    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }

    return dist[n];
}  

int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    if(spfa()==0x3f3f3f3f) printf("impossible");
    else printf("%d",spfa());
}



题目描述

给定n个正整数ai,判定每个数是否是质数。

输入格式
第一行包含整数n。

接下来n行,每行包含一个正整数ai。

输出格式
共n行,其中第 i 行输出第 i 个正整数ai是否为质数,是则输出“Yes”,否则输出“No”。

数据范围
1≤n≤100,
1≤ai≤2∗109

样例

输入样例:
2
2
6
输出样例:
Yes
No

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,a[110];

bool pdzs(int m){
    for(int i=2;i<=sqrt(m);i++){
    /*
    只需枚到m开根号取整就行
    一个数n如果不是素数那么一定存在若干因子(不少于2个)
    假设最小的因子是p,那么p*p<=n,所以p<根号n
    只要找到不为1的p,它就不是质数
    */
        if(m%i==0) return false;
    }
    return true;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        if(a[i]==2)//2是特殊的质数,需要特判
        {
            printf("Yes\n");
            continue;
        }
        if(a[i]<=1)//小于等于的数1既不是质数,也不是合数,需要特判
        {
            printf("No\n");
            continue;
        }
        bool b=pdzs(a[i]);//判断a[i]是不是质数
        if(b==true) printf("Yes\n");
        else printf("No\n");
    }
}



#include<bits/stdc++.h>
using namespace std;
int n,a[110];

bool pdzs(int m){
    for(int i=2;i<=sqrt(m);i++){
    /*
    只需枚到m开根号取整就行
    一个数n如果不是素数那么一定存在若干因子(不少于2个)
    假设最小的因子是p,那么p*p<=n,所以p<根号n
    只要找到不为1的p,它就不是质数
    */
        if(m%i==0) return false;
    }
    return true;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        if(a[i]==2)//2是特殊的质数,需要特判
        {
            printf("Yes\n");
            continue;
        }
        if(a[i]==1)
        {
            printf("No\n");
            continue;
        }
        bool b=pdzs(a[i]);//判断a[i]是不是质数
        if(b==true) printf("Yes\n");
        else printf("No\n");
    }
}



#include<bits/stdc++.h>
using namespace std;
const int N=510,M=10010;
struct Edge{
    int a;
    int b;
    int w;
}e[M];
int dist[N];
int back[N];
int n,m,k;

int bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++){
        memcpy(back,dist,sizeof dist);
        for(int j=0;j<m;j++){
            int a=e[j].a,b=e[j].b,w=e[j].w;
            dist[b]=min(dist[b],back[a]+w);
        }

    }
    if(dist[n]>0x3f3f3f3f/2) return -1;
    else return dist[n];

}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        e[i]={a,b,w};
    }
    if(bellman_ford()==-1) printf("impossible");
    else printf("%d",bellman_ford());
}