精华内容
下载资源
问答
  • 二分图染色(二分图的判断方法) 二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个...

    二分图染色(二分图的判断方法)


    二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。
    在这里插入图片描述
    而对于二分图的判定,一般采用染色法。代码如下:

    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<vector>
    #include<queue>
    #include<cstdio>
    #include<set>
    #include<cstdlib>
    using namespace std;
    vector<int>g[200005];//通过邻接表的方式存储可以存入更多的点
    int color[200005];//存储当前点的颜色
    int bfs(int u);
    int main()
    {
    	    int n,m,x,y,i;
    		cin>>n>>m;
    		for(i=0;i<n;i++)
    		{
    			g[i].clear();
    			color[i]=0;//初始化,表示当前点未染色
    		}
    		for(i=0;i<m;i++)
    		{
    			scanf("%d%d",&x,&y);
    			g[x].push_back(y);
    			g[y].push_back(x);
    		}
    		if(bfs(1))printf("YES\n");
    		else printf("NO");
    }
    int bfs(int u)
    {
    	queue<int>q;
    	q.push(u);
    	color[u]=1;
    	while(!q.empty())
    	{
    		int t=q.front();
    		q.pop();
    		for(int i=0;i<g[t].size();i++)
    		{
    			if(color[g[t][i]]==color[t])return 0;//如果当前点和该点相连的另一点的颜色相同,那么证明该图不是二分图
    			else if(!color[g[t][i]])//如果不相等,且当前点未染色,那么进行染色,并将该点推入队列中
    			{
    				color[g[t][i]]=-color[t];
    				q.push(g[t][i]);
    			}
    		}
    	}
    	return 1;
    }
    
    展开全文
  • 二分图染色

    2018-03-08 13:08:00
    也可以用二分图染色+二分答案 每次找到一个怒气值将比此怒气值大的连个点连边 然后dfs染色 如果二分图染色合法则此怒气值可行 做法如下: #include&lt;iostream&gt; #include&lt;cstdio&gt; #...

    luogu1525 关押罪犯
    可以用并查集
    也可以用二分图染色+二分答案
    每次找到一个怒气值将比此怒气值大的连个点连边
    然后dfs染色
    如果二分图染色合法则此怒气值可行
    做法如下:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define maxn 100005
    using namespace std;
    int n,m,cnt,head[maxn],clo[maxn],ans,ci[maxn];
    bool used[maxn],flag;
    
    struct joi{
        int frm,to,w;
    }per[maxn];
    
    struct node{
        int to,nxt;
    }edge[maxn*2];
    
    bool cmp(joi x,joi y)
    {
        return x.w>y.w;
    }
    
    void add(int x,int y)
    {
        cnt++;
        edge[cnt].to=y;
        edge[cnt].nxt=head[x];
        head[x]=cnt;
    }
    
    bool dfs(int x,int cl)//染色 
    {
        clo[x]=cl;
        for(int i=head[x];i;i=edge[i].nxt)
        {
            int v=edge[i].to;
            if(clo[v]==cl) flag=false;
            else if(!clo[v]) dfs(v,3-cl);
        }
    }
    
    bool judge(int x)
    {
        for(register int i=1;i<x;i++)
        {
            if(!clo[per[i].frm])
            {
                flag=true;
                dfs(per[i].frm,1); 
                if(!flag) return false;
            }
        }
        return true;
    }
    
    
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&per[i].frm,&per[i].to,&per[i].w);
        }
        sort(per+1,per+m+1,cmp);
        int l=1,r=m+1;
        while(l+1<r)//二分答案一个冲突值,比它大的连边,将作出的图二分图染色,如果可行,继续寻找更小的答案 
        {
            memset(clo,0,sizeof clo);
            memset(head,0,sizeof head);
            cnt=0;
            int mid=(l+r)>>1;
            for(register int i=1;i<mid;i++)
            {
                add(per[i].frm,per[i].to); add(per[i].to,per[i].frm);//连边 
            }
            if(judge(mid)) {ans=per[mid].w;l=mid;}
            else r=mid;
        }
        if(l==m+1) printf("0\n");//如果最低怒气值仍合法输出0 
        else printf("%d\n",ans);
        return 0;
    }
    展开全文
  • 【二分图判定】二分图染色

    千次阅读 2018-08-07 13:26:54
    二分图判定有两点。 1、图为连通图。 2、可以分为两个不同的点集。 二分图的另一种等价的说法是,可以把每个节点着以黑色和白色之一,使得每条边的两个端点颜色不同.不难发现,非连通的图是二分图当且仅当每个...

    二分图判定有两点。
    1、图为连通图。
    2、可以分为两个不同的点集。
    二分图的另一种等价的说法是,可以把每个节点着以黑色和白色之一,使得每条边的两个端点颜色不同.不难发现,非连通的图是二分图当且仅当每个连通分量都是二分图,因此我们只考虑无向连通图。
    连通图判断方式

    #include<cstdio>
    #include<algorithm>
    #define N 42000
    int next[N],to[N],num,head[N],col[N],flag,n,m,a,b;
    void add(int false_from,int false_to){
        next[++num]=head[false_from];
        to[num]=false_to;
        head[false_from]=num;
    }
    void dfs(int x,int color){
        col[x]=color;
        for(int i=head[x];i;i=next[i]){
            if(col[to[i]]==col[x]){
                printf("NO");
                flag=1;
                exit(0);
            }
            if(!col[to[i]])
                dfs(to[i],-color);
        }
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;++i){
            scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
        dfs(1,1);
        if(!flag)
            printf("YES");
        return 0;
    }

    非连通图判断方式。

    #include<cstdio>
    #include<algorithm>
    #define N 42000
    int next[N],to[N],num,head[N],col[N],flag,n,m,a,b;
    void add(int false_from,int false_to){
        next[++num]=head[false_from];
        to[num]=false_to;
        head[false_from]=num;
    }
    void dfs(int x,int color){
        col[x]=color;
        for(int i=head[x];i;i=next[i]){
            if(col[to[i]]==col[x]){
                printf("NO");
                flag=1;
                exit(0);
            }
            if(!col[to[i]])
                dfs(to[i],-color);
        }
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;++i){
            scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
        for(int i=1;i<=n&&!flag;++i)
            if(!col[i])
                dfs(i,1);
        if(!flag)
            printf("YES");
        return 0;
    }
    展开全文
  • 二分图染色(弱化版) 给定一个完全二分图,图的左右两边的顶点数目相同。我们要给图中的每条边染成红色、蓝色、或者绿色,并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。 计算所有满足条件的染色的...

    二分图染色(弱化版)

    给定一个完全二分图,图的左右两边的顶点数目相同。我们要给图中的每条边染成红色、蓝色、或者绿色,并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。
    计算所有满足条件的染色的方案数,并对10^9+7取模。

    输入描述:

    二分图单边的顶点数目n(n ≤ 10^7)

    输出描述:

    输出一个整数,即所求的答案。

    输入

    2

    输出

    35

    二分图转换为棋盘问题

    两边不共享端点的问题可以转化为棋盘模型,即在 n n n × \times × n n n 的棋盘上放红蓝棋子,每个格子至多放一次,同行同列的棋子不能同色,显然,对于每一种颜色我们有 F n F_{n} Fn = ∑ i = 0 n \sum_{i=0}^n i=0n C n i C_{n}^{i} Cni A n i A_{n}^{i} Ani 种放置方案。

    考虑两种颜色同时存在,此时 F n F_{n} Fn × \times × F n F_{n} Fn 中包含这两种颜色同方格的情况,因此我们考虑容斥减掉这部分,最终结果为: ∑ i = 0 n \sum_{i=0}^n i=0n ( − 1 ) n (-1)_{}^{n} (1)n C n i C_{n}^{i} Cni A n i A_{n}^{i} Ani ( F n − i ) 2 (F_{n-i})_{}^{2} (Fni)2

    随后考虑 F n F_{n} Fn 从前一个状态 F n − 1 F_{n-1} Fn1 的转移,即在格子的第 n n n 行的 n n n 个空中,我们可以染或者不染某一个方格,该方案数为 2 n 2n 2n × \times × F n − 1 F_{n-1} Fn1 ,但是第 n n n 行的染色操作可能会与之前 n − 1 n-1 n1 行中的某个方案冲突,横向 n − 1 n-1 n1 个格子,纵向 n − 1 n-1 n1 行,总方案数 ( n − 1 ) 2 (n-1)_{}^{2} (n1)2 × \times × F n − 2 F_{n-2} Fn2

    因此对于 F n F_{n} Fn,有递推公式 F n F_{n} Fn= 2 n 2n 2n × \times × F n − 1 F_{n-1} Fn1 − - ( n − 1 ) 2 (n-1)_{}^{2} (n1)2 × \times × F n − 2 F_{n-2} Fn2

    代码
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <iostream>
    #include <regex>
    
    using namespace std;
    
    #define ll long long
    const int maxn = 1e7 + 10;
    const int mod = 1e9 + 7;
    ll mul[maxn];
    ll inv[maxn];
    ll f[maxn];
    
    void init() {
        mul[0] = 1;
        for (int i = 1; i < maxn; i++) {
            mul[i] = (mul[i - 1] * i) % mod;
        }
        inv[0] = inv[1] = 1;
        for (int i = 2; i < maxn; i++) {
            inv[i] = (ll) (mod - mod / i) * inv[mod % i] % mod;
        }
        for (int i = 1; i < maxn; i++) {
            inv[i] = (inv[i - 1] * inv[i]) % mod;
        }
        f[0] = 1;
        f[1] = 2;
        for (int i = 2; i < maxn; i++) {
            f[i] = 2ll * i * f[i - 1] % mod - 1ll * (i - 1) * (i - 1) % mod * f[i - 2] % mod;
            f[i] = (f[i] % mod + mod) % mod;
        }
    }
    
    ll C(int n, int m) {
        return mul[n] * inv[m] % mod * inv[n - m] % mod;
    }
    
    ll A(int n, int m) {
        return mul[n] * inv[n - m] % mod;
    }
    
    void solve(int n) {
        ll ans = 0;
        for (int i = 0; i <= n; i++) {
            ans += ((i & 1) ? -1LL : 1LL) * C(n, i) * A(n, i) % mod * f[n - i] % mod * f[n - i] % mod;
            ans = (ans % mod + mod) % mod;
        }
        cout << ans << endl;
    }
    
    int main() {
        init();
        int n;
        cin >> n;
        solve(n);
        return 0;
    }
    
    展开全文
  • 二分图染色 题目链接 题解链接 题目描述 给定一个完全二分图,图的左右两边的顶点数目相同。我们要给图中的每条边染成红色、蓝色、或者绿色,并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。 计算...
  • 二分图定义 二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,...
  • ( 图论专题 )【 二分图染色 】 二分图的判定方式:图中没有边数为奇数的环。 二分图的另一种等价的说法是,可以把每个节点着以黑色和白色之一,使得每条边的两个端点颜色不同。 不难发现,非连通的图是二分图...
  • 染色问题用什么去实现 : dfs 染色: 一旦给一个点染上颜色,其所在的连通部分中的所有点都要被染上颜色...注意: 题所给的不一定是连通。 class Solution { public: bool dfs(vector<vector<int>...
  • 二分图染色实例

    2019-06-22 13:47:54
    二分图染色实例 二分图染色水题——CF 解决图的问题的时候先考虑的就是建图 一、邻接矩阵 这道题的数据不支持用二维数组建图,但不要为了做题而做题嘛。我特地用邻接矩阵WA一次。 直接上代码: 这里的结果是WA...
  • 二分图染色模板

    2020-06-17 20:10:31
    判定一个图是否为二分图 从其中一个定点开始,将跟它邻接的点染成与其不同的颜色,最后如果邻接的点有相同颜色,则说明不是二分图,每次用bfs或者bfs遍历即可。 dfs模板 bool dfs(int u,int c){ color[u]=c; for...
  • 给定一个完全二分图,图的左右两边的顶点数目相同。我们要把图中的每条边染成红色、蓝色、或者绿色,并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。计算所有满足条件的染色的方案数,并对10^9+7取模...
  • C++:二分图染色法---双栈排序

    千次阅读 多人点赞 2016-09-21 14:06:04
    所示,通过2个栈S1和S2,Tom希望借助以下4种操作实现将输入序列升序排序。操作a:如果输入序列不为空,将第一个元素压入栈S1 操作b:如果栈S1不为空,将S1栈顶元素弹出至输出序列 操作c:如果输入序列不为空,...
  • 题目链接 题意: 给你n, m, x, y四个数,n代表编号,接...二分图染色问题,注意读题; 在已知的好人坏人中第一遍DFS,在余下的图中未知的位置,分别填上好人坏人的条件下看看是否都矛盾;#include #include <cstrin
  • 二分图染色[容斥]

    2020-12-02 18:43:21
    思路:可以看成可以转化为棋盘染色问题 相当于每一行/每一列同一种颜色只能放一个,并且格子颜色不能重复 然后考虑只有一种颜色的答案 显然为: fn=∑i=0n(ni)2i!f_n=\sum_{i=0}^n \binom{n}{i}^2i!fn​=i=0∑n​(in...
  • 进行二分图染色判定即可,若是二分图,则满足条件,反之则不满足   注意题目给的有向边,需要将没有双向边的单向边建一条无向边来进行判断是否是二分图。 #include using namespace std; const int N=...
  • 题目链接 题目含义 ...二分图染色模板题 注意这里二分代表的两个集合都是n个学生,如果你建双向边,最后最大匹配数要除2 题目代码 #include<iostream> #include<stdio.h> #incl...
  • 给定n个点m条边的无向(开始每个点都是白色) 下面m行给出边和边权,边权表示这条边所连接的2个点中被染成黑色的点数。 0表示染,1表示其中一个点染,2表示都染。 问:最少染多少个点可以满足上述的边权。若不...
  • 题目:二分图染色(弱化版) 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 524288K,其他语言1048576K 64bit IO Format: %lld 题目描述 给定一个完全二分图,图的左右两边的顶点数目相同。我们要给图中的每条...
  • dp、容斥
  • POJ 2492 a bug’s life [并查集||二分图染色]题目链接:POJ点此进入链接 HDU点此进入链接 A Bug’s Life Time Limit: 10000MS Memory Limit: 65536K Total Submissions: 32887 Accepted: 10772 ...
  • 并查集与二分图染色法 原理:把相同颜色的放进一个联通集合里面,建立一个数组,记录与根不相同的节点。 具体请看代码: P1525 #include <bits/stdc++.h> using namespace std; #define FR freopen("in.txt...
  • 传送门 发这篇只是为了记录一个容易TLE的坑点:对于这种多组数据,所有数据n之和不超过3e5的题,初始化的时候要for 1 to n,而不能memset,否则比如30000组数据每组n为10,那么如果memset进行30000次的复杂度就会炸...
  • 分析:根据所给关系建图,因为点数可能,所以用maxn记录最大点数,建好图后dfs给图染色,如果染色成功,遍历每个点记录颜色不同的点,染色失败则输出-1。 代码如下: #include #include #include #...
  • 给你一张n个点m条边的无向连通图(没有边权)。保证图中没有重边和自环 你的任务是选择至多⌊n/2​⌋个点使得对于任意一个没有被选择的点都和至少一个...如此一来就转化成了二分图染色。最后看一下是哪种颜色满足&l

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,226
精华内容 2,490
关键字:

二分图染色