头像

wuwendongxi

抓 颓 警 告!| $\href{https://www.luogu.com.cn/user/299811}{QwQ}$




离线:3小时前


最近来访(119)
用户头像
蓝鲸
用户头像
JayZ
用户头像
科宇
用户头像
王义飞
用户头像
leimingze
用户头像
WuHeng_akNOIP
用户头像
小涛涛
用户头像
简遇而安
用户头像
Coisi
用户头像
KkkkkkkkkKK
用户头像
消灭dp暴政世界属于记搜-东方风云榜第一-看题宰题虐题王冲鸭
用户头像
ArkhamKnight
用户头像
大雪莱
用户头像
ssuunn
用户头像
白墙
用户头像
自律
用户头像
CZ-7
用户头像
CLOVER
用户头像
浙江星辰
用户头像
吴子涵

新鲜事 原文

wuwendongxi
16小时前
去年的RP帖还有人赞 今年继续RP++ https://www.acwing.com/file_system/file/content/whole/index/content/1431445/


新鲜事 原文

更新了头像~



已解决,感谢~

最后再提问一次,相关问题这个贴说明了:

https://www.acwing.com/community/content/618950/

摘录一下:

调这道题时:

https://www.acwing.com/problem/content/description/367/

大概思路:建补图-割点-点双连通图-判奇环-输出(详细的思路看第一篇题解吧)

只有一个大的离谱的数据,输出了一下,发现标称第一个组数据有19个点双连同分量,我的只有12个

7行tarjan代码戳原帖

不一定要帮我调代码,指出一下关于tarjan的问题,或者给组小一点的hack数据就行

求求了 QwQ

完整代码附一个(很短,比题解区3k以上的代码好看多了):(其他有小样例的OJ测了一下90分,大体没有问题,但大数据过不了)

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2003;
bool lk[maxn][maxn],tag[maxn];
int n,m,head[maxn],cnt,dfn[maxn],low[maxn],sta[maxn],idx,num,bel[maxn],siz[maxn],vis[maxn],ans;
struct node{int next,to;}e[4000003];
void addedge(int x,int y){e[++cnt]=(node){head[x],y},head[x]=cnt;}
void tarjan(int x,int pre){//tarjan缩点
    dfn[x]=low[x]=++cnt;sta[++idx]=x;
    for(int i=head[x],v;v=e[i].to,i;i=e[i].next) if(v!=pre)
        if(!dfn[v]) tarjan(v,x),low[x]=min(low[x],low[v]);
        else low[x]=min(low[x],dfn[v]);
    if(low[x]==dfn[x]) for(++num;sta[idx+1]!=x;--idx) bel[sta[idx]]=num,siz[num]++;
}
bool dfs(int x,int col){//2分图染色判奇环
    vis[x]=col;
    for(int i=head[x],v;v=e[i].to,i;i=e[i].next)
    if(bel[v]==bel[x])
        if(!vis[v]) return dfs(v,3-col);
        else if(vis[v]==col) return 1;
    return 0;
}
int main()
{
    while(scanf("%d%d",&n,&m),n||m){
        for(int i=1;i<=n;++i){
            head[i]=dfn[i]=low[i]=siz[i]=vis[i]=tag[i]=sta[i]=0;
            for(int j=i+1;j<=n;++j) lk[i][j]=lk[j][i]=0;
        }idx=num=ans=0,cnt=1;
        for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),lk[u][v]=lk[v][u]=1;
        for(int i=1;i<n;++i) for(int j=i+1;j<=n;++j) if(!lk[i][j]) addedge(i,j),addedge(j,i);
        cnt=0;for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,0);
        for(int i=1,tmp;i<=n;++i) if(!tag[bel[i]]) tag[bel[i]]=1,tmp=dfs(i,1),ans+=tmp*siz[bel[i]];
        cout<<n-ans<<'\n';
    }
    return 0;
}

小声bb:拼团链接能不能不要放提问分享里占版面呐,放新鲜事就够辣!!!




来张随机图~更多戳这里

图片走丢辣~

小声bb:本来不想发分享,但新鲜事Md好像用不了




调这道题:

https://www.acwing.com/problem/content/description/367/

大概思路:建补图-割点-点双连通图-判奇环-输出
详细的思路看第一篇题解吧

只有一个大的离谱的数据,输出了一下,发现标称第一个组数据有19个点双连同分量,我的只有12个

tarjan找点双连同分量如下:

void tarjan(int x,int pre){
    dfn[x]=low[x]=++cnt;sta[++idx]=x;
    for(int i=head[x],v;v=e[i].to,i;i=e[i].next) if((i^1)^pre)
        if(!dfn[v]) tarjan(v,i),low[x]=min(low[x],low[v]);
        else low[x]=min(low[x],dfn[v]);
    if(low[x]==dfn[x]) for(++num;sta[idx+1]!=x;--idx) bel[sta[idx]]=num,siz[num]++;
}

求求了,给一组hack数据也可以啊



新鲜事 原文

wuwendongxi
10个月前
祝RP++


新鲜事 原文

wuwendongxi
10个月前
连以前写了题解的题目都看不到了


新鲜事 原文

wuwendongxi
10个月前
差评、acwing不报名不给题


新鲜事 原文

wuwendongxi
10个月前
虽然已经过了,但还是来存个图
图片


新鲜事 原文

wuwendongxi
2020-09-08 07:48
之前好像问了一个问题,dp和搜索能否互换 [链接](https://www.acwing.com/file_system/file/content/whole/index/content/1117315/) 记得当时想了很久 后来突然想到这俩最大的一个差别:一个枚举所有方案,一个只求方案数 真是学数据结构学傻了。。。