头像

xiuzhiyuan




离线:17分钟前


最近来访(321)
用户头像
我要出去乱说
用户头像
caishannuo
用户头像
一万小时定律
用户头像
Cabbage74
用户头像
AcWing2AK
用户头像
.CHY
用户头像
封号用户
用户头像
凌钧
用户头像
种花家的兔兔
用户头像
超级酷在线coding
用户头像
宋君婉
用户头像
六角星
用户头像
用户头像
RC.阿柒
用户头像
Quinn
用户头像
铁锅炖大鹅
用户头像
mmmmm
用户头像
狂气电波
用户头像
白菜Cabbage
用户头像
AC-黑白

新鲜事 原文

xiuzhiyuan
20分钟前
22222



#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct edge{
    int f,t,w;
    bool operator<(const edge &W)const{
        return w<W.w;
    }
}edges[4955];
int n,m,fa[105];
bool dele[4955],univis[4955];
int find(int x){
    if(fa[x]!=x)
        fa[x]=find(fa[x]);
    return fa[x];
}
int kr(bool change){
    for(int i=1;i<=n;i++)
        fa[i]=i;
    int res=0;
    for(int i=1;i<=m;i++){
        int a=find(edges[i].f),b=find(edges[i].t);
        if(a!=b&&!dele[i]){
            res+=edges[i].w;
            fa[b]=a;
            if(change)
                univis[i]=1;
        }
    }
    return res;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(univis,0,sizeof univis);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
            scanf("%d %d %d",&edges[i].f,&edges[i].t,&edges[i].w);
        sort(edges+1,edges+1+m);
        int ans=kr(1);
        bool flag=1;
        for(int i=1;i<=m;i++)
            if(univis[i]){
                dele[i]=1;
                if(kr(0)==ans){
                    dele[i]=0;
                    flag=0;
                    break;
                }
                dele[i]=0;
            }
        if(flag)
            printf("%d\n",ans);
        else
            puts("Not Unique!");
    }
    return 0;
}


活动打卡代码 AcWing 4230. 逃跑

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=105;
struct node{
    int x,y,t;
};
queue<node> que;
bool map[N][N][1005];
int gtw[N],gt[N],gv[N],gx[N],gy[N];
int xx[5]={0,0,1,-1,0},yy[5]={-1,1,0,0,0};
int main(){
    int n,m,k,d;
    while(scanf("%d%d%d%d",&n,&m,&k,&d)==4){
        while(que.size())
            que.pop();
        memset(map,0,sizeof map);
        for(int i=0;i<k;i++){
            char tw[2];
            scanf("%s%d%d%d%d",tw,&gt[i],&gv[i],&gy[i],&gx[i]);
            for(int j=0;j<=d;j++)
                map[gx[i]][gy[i]][j]=1;
            if(tw[0]=='N')
                gtw[i]=0;
            else if(tw[0]=='S')
                gtw[i]=1;
            else if(tw[0]=='E')
                gtw[i]=2;
            else if(tw[0]=='W')
                gtw[i]=3;
        }
        for(int i=0;i<k;i++){
            int x=gx[i],y=gy[i],dis=0;
            while(1){
                x+=xx[gtw[i]];
                y+=yy[gtw[i]];
                dis++;
                if(x<0||x>m||y<0||y>n||map[x][y][0])
                    break;
                if(dis%gv[i]==0)
                    for(int j=dis/gv[i];j<=d;j+=gt[i])
                        map[x][y][j]=1;
            }
        }
        que.push({0,0,0});
        bool flag=1;
        while(que.size()&&flag){
            node now=que.front();
            que.pop();
            int x=now.x,y=now.y,t=now.t+1;
            for(int i=0;i<5;i++){
                int a=x+xx[i],b=y+yy[i];
                if(a<0||a>m||b<0||b>n||map[a][b][t])
                    continue;
                map[a][b][t]=1;
                if(n-x+m-y>d-t)
                    continue;
                if(a==m&&b==n){
                    printf("%d\n",t);
                    flag=0;
                    break;
                }
                que.push({a,b,t});
            }
        }
        if(flag)
            puts("Bad luck!");
    }
    return 0;
}


活动打卡代码 AcWing 3409. 这是一棵树吗

#include<iostream>
#include<cstring>
using namespace std;
int fa[10005],ru[10005];
bool vis[10005];
int find(int x){
    if(fa[x]!=x)
        fa[x]=find(fa[x]);
    return fa[x];
}
int main(){
    int a,b,bcnt=0,dcnt=0;
    int cnt=0;
    bool ok=1;
    for(int i=1;i<10000;i++)
        fa[i]=i;
    while(scanf("%d%d",&a,&b))
        if(a==-1)
            return 0;
        else if(!a){
            if((bcnt!=dcnt-1||!ok)&&bcnt!=0)
                printf("Case %d is not a tree.\n",++cnt);
            else
                printf("Case %d is a tree.\n",++cnt);
            for(int i=1;i<10000;i++)
                fa[i]=i;
            bcnt=dcnt=0;
            memset(vis,0,sizeof vis);
            memset(ru,0,sizeof ru);
            ok=1;
        }
        else{
            if(find(b)==find(a))
                ok=0;
            if(!vis[a])
                dcnt++;
            if(!vis[b])
                dcnt++;
            vis[a]=vis[b]=1;
            ru[b]++;
            if(ru[b]>=2)
                ok=0;
            fa[find(b)]=find(a);
            bcnt++;
        }
}


新鲜事 原文

问题,如果回复了评论,就只能在动态里看。 问答,就只能在问答里看。



AcWing 3409.这是一棵树吗

悬赏0AC币提问:

这段代码为啥会错?

#include<iostream>
#include<cstring>
using namespace std;
int fa[10005];
bool vis[10005];
int find(int x){
    if(fa[x]!=x)
        fa[x]=find(fa[x]);
    return fa[x];
}
int main(){
    int a,b,bcnt=0,dcnt=0;
    int cnt=0;
    bool ok=1;
    for(int i=1;i<10000;i++)
        fa[i]=i;
    while(scanf("%d%d",&a,&b))
        if(a==-1)
            return 0;
        else if(!a){
            if((bcnt!=dcnt-1||!ok)&&bcnt!=0)
                printf("Case %d is not a tree.\n",++cnt);
            else
                printf("Case %d is a tree.\n",++cnt);
            for(int i=1;i<10000;i++)
                fa[i]=i;
            bcnt=dcnt=0;
            memset(vis,0,sizeof vis);
            ok=1;
        }
        else{
            if(find(b)==find(a))
                ok=0;
            if(!vis[a])
                dcnt++;
            if(!vis[b])
                dcnt++;
            vis[a]=vis[b]=1;
            fa[find(b)]=find(a);
            bcnt++;
        }
}


活动打卡代码 AcWing 367. 学校网络

#include<iostream>
using namespace std;
const int N=105,M=10005;
int h[N],to[M],ne[M],idx=1;
int block[N],bcnt;
int in[N],out[N];
bool inst[N];
int dft[N],low[N],nowt;
int s[N],tt;
void add(int x,int y){
    to[idx]=y,ne[idx]=h[x],h[x]=idx++;
}
void dfs(int x){
    dft[x]=low[x]=++nowt;
    s[++tt]=x,inst[x]=1;
    for(int i=h[x];i;i=ne[i])
        if(!dft[to[i]]){
            dfs(to[i]);
            low[x]=min(low[x],low[to[i]]);
        }
        else if(inst[to[i]])
            low[x]=min(low[x],low[to[i]]);
    if(dft[x]==low[x]){
        ++bcnt;
        int now;
        do{
            now=s[tt--];
            block[now]=bcnt;
            inst[now]=0;
        }while(now!=x);
    }
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int to;
        while(scanf("%d",&to),to)
            add(i,to);
    }
    for(int i=1;i<=n;i++)
        if(!dft[i])
            dfs(i);
    for(int i=1;i<=n;i++)
        for(int j=h[i];j;j=ne[j]){
            int a=block[i],b=block[to[j]];
            if(a!=b)
                out[a]++,in[b]++;
        }
    int scnt=0,tcnt=0;
    for(int i=1;i<=bcnt;i++){
        if(in[i]==0)
            scnt++;
        if(out[i]==0)
            tcnt++;
    }
    printf("%d\n",scnt);
    if(bcnt==1)
        puts("0");
    else
        printf("%d",max(scnt,tcnt));
    return 0;
}


活动打卡代码 AcWing 4295. QS网络

#include<iostream>
#include<algorithm>
using namespace std;
const int N=505,M=250005;
struct edge{
    int f,t,w;
    bool operator<(const edge &W)const{
        return w<W.w;
    }
}edges[M];
int idx,fa[N],p[N];
int find(int x){
    if(fa[x]!=x)
        fa[x]=find(fa[x]);
    return fa[x];
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,ans=0;
        idx=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            fa[i]=i;
        for(int i=1;i<=n;i++)
            scanf("%d",&p[i]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                int w;
                scanf("%d",&w);
                edges[idx++]={i,j,w+p[i]+p[j]};
            }
        sort(edges,edges+idx);
        for(int i=0;i<idx;i++)
            if(find(edges[i].f)!=find(edges[i].t)){
                ans+=edges[i].w;
                fa[find(edges[i].t)]=find(edges[i].f);
            }
        printf("%d\n",ans);
    }
    return 0;
}


活动打卡代码 AcWing 4294. 修建道路

#include<iostream>
#include<algorithm>
using namespace std;
struct edge{
    int f,t,w;
    bool operator<(const edge &W)const{
        return w<W.w;
    }
}edges[10005];
int idx,fa[105];
int find(int x){
    if(fa[x]!=x)
        fa[x]=find(fa[x]);
    return fa[x];
}
int main(){
    int n,q,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            int w;
            scanf("%d",&w);
            edges[idx++]={i,j,w};
        }
    scanf("%d",&q);
    while(q--){
        int a,b;
        scanf("%d%d",&a,&b);
        fa[find(b)]=find(a);
    }
    sort(edges,edges+idx);
    for(int i=0;i<idx;i++)
        if(find(edges[i].f)!=find(edges[i].t)){
            ans+=edges[i].w;
            fa[find(edges[i].t)]=find(edges[i].f);
        }
    printf("%d",ans);
    return 0;
}


活动打卡代码 AcWing 4292. 网络连接

#include<iostream>
#include<algorithm>
using namespace std;
const int N=55,M=3005;
struct edge{
    int f,t,w;
    bool operator<(const edge &W)const{
        return w<W.w;
    }
}edges[M];
int idx,fa[N];
int find(int x){
    if(fa[x]!=x)
        fa[x]=find(fa[x]);
    return fa[x];
}
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)==2){
        for(int i=1;i<=n;i++)
            fa[i]=i;
        idx=0;
        while(m--){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            edges[idx++]={a,b,c};
            edges[idx++]={b,a,c};
        }
        sort(edges,edges+idx);
        int ans=0;
        for(int i=0;i<idx;i++)
            if(find(edges[i].f)!=find(edges[i].t)){
                fa[find(edges[i].t)]=find(edges[i].f);
                ans+=edges[i].w;
            }
        printf("%d\n",ans);
    }
    return 0;
}