文档章节

图论:二分图判定

o
 osc_4nmshwhm
发布于 2018/08/06 22:39
字数 625
阅读 9
收藏 0

精选30+云产品,助力企业轻松上云!>>>

我其实只是想练一练二分图判定的,但是翻到了一个这么个题。。

双栈排序早有耳闻,非常欣赏当年的出题水平,堪称经典

 

这个题AC的人一定是个天才

废话不多说,双栈排序的思路我就不介绍了,没有那个水平,直接来说说怎么二分图染色

bool color(int x,int cl)
{
    c[x]=cl;
    for(int tmp=g[x];tmp;tmp=e[tmp].next)
    {
        if(!c[e[tmp].t])
            {if(!color(e[tmp].t,3-cl)) return 0;}
        else if(c[e[tmp].t]==cl) return 0;
    }
    return 1;
}

这个方法,14年的时候练了很多次,当时习惯写BFS的,可能是因为所有点都要跑所以无所谓了吧

每个点都调用一次color,初始cl传1,进来的时候如果这个点没有染过色,就给它染上cl这个颜色

然后判断所有出边所连接的点,如果有相邻且同色的,直接GG

否则,染色为3-cl,这是一个小技巧,cl这时取值为1或2,十分方便

好了,二分图判定说完了,贴上双栈排序的代码跑路了

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int INF=1000000000;
 5 const int maxn=1005;
 6 int cnt,n,t1,t2;
 7 int a[maxn],g[maxn],c[maxn],f[maxn],s1[maxn],s2[maxn];
 8 struct Edge{int t,next;}e[maxn*maxn];
 9 void addedge(int u,int v)
10 {
11     e[++cnt].t=v;e[cnt].next=g[u];
12     g[u]=cnt;
13 }
14 bool color(int x,int cl)
15 {
16     c[x]=cl;
17     for(int tmp=g[x];tmp;tmp=e[tmp].next)
18     {
19         if(!c[e[tmp].t])
20             {if(!color(e[tmp].t,3-cl)) return 0;}
21         else if(c[e[tmp].t]==cl) return 0;
22     }
23     return 1;
24 }
25 int read()
26 {
27     int x=0,f=1;char ch=getchar();
28     while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
29     while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
30     return x*f;
31 }
32 int main()
33 {
34     n=read();
35     for(int i=1;i<=n;i++) a[i]=read();
36     f[n+1]=INF;
37     for(int i=n;i;i--) f[i]=min(f[i+1],a[i]);
38     for(int i=1;i<=n;i++)
39         for(int j=i+1;j<=n;j++)
40             if(a[i]<a[j]&&f[j+1]<a[i]) addedge(i,j),addedge(j,i);
41     for(int i=1;i<=n;i++)
42         if(!c[i])
43             if(!color(i,1)) {puts("0");return 0;}
44     int now=1;
45     for(int i=1;i<=n;i++)
46     {
47         if(c[i]==1) printf("a "),s1[++t1]=a[i];
48         else printf("c "),s2[++t2]=a[i];
49         while(s1[t1]==now||s2[t2]==now)
50         {
51             if(s1[t1]==now) printf("b "),t1--;
52             else printf("d "),t2--;
53             now++;
54         }
55     }
56     return 0;
57 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

土木转行Python的几个方向? - 知乎

零、背景 近一段时间有不少土木或兄弟专业的朋友加微信问我,自学Python一段时间后又出现了迷茫期,怎么破?不知道接下来走向哪里?下面,我把我知道的告诉你,至于Python之父是不是廖雪峰,...

osc_2ak6wwpl
24分钟前
0
0
如何选购便宜的SSL证书

我们在购物的时候经常会货比三家,而价格会占主导因素,有时候价格太高会让我们望而却步。而在选购SSL证书的时候也是同样的道理,市面上可供选择的SSL证书品牌和类型繁多,价格有高有低,那么...

安信证书
25分钟前
5
0
Spark SQL 中 Broadcast Join 一定比 Shuffle Join 快?那你就错了。

本资料来自 Workday 的软件开发工程师 Jianneng Li 在 Spark Summit North America 2020 的 《On Improving Broadcast Joins in Spark SQL》议题的分享。 文章目录 1 背景 2 TPC-H 测试 3 Br...

osc_k8v7r34l
26分钟前
13
0
空间直线与球面相交算法

目录 1. 原理推导 1.1. 直线公式 1.2. 求交 2. 具体实现 3. 参考 1. 原理推导 1.1. 直线公式 在严格的数学定义中,直线是无线延长,没有端点的线;射线是一端有端点,另外一段没有端点无线延...

osc_nfjwhlc1
26分钟前
15
0
七天用Go写个docker(第六天)

今天主要来实现一下 go-docker ps 的功能,也就是查看当前有哪些容器,简单说下思路,当我们启动一个容器时就为该容器创建一个文件夹用来保存该容器的一些信息,如果我们给容器指定了名字,那...

osc_zsaazovz
28分钟前
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部