二分图总结

在二分图中

题目一    染色法

题目链接：https://www.acwing.com/problem/content/259/

思路：二分check  然后判是否能成为二分图， 大于mid 的边可以不用判

 1 #include
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 const int mod=998244353;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pb push_back
 8 #define pi pair
 9 #define fi first
10 #define sc second
11 
12 int n,m;
13 vectorE[maxn];
14 int col[maxn];
15 int f;
16 
17 void dfs(int u,int c,int k)
18 {
19     col[u]=c;
20     for(auto &v:E[u])
21     {
22         if(v.sc<=k) continue;
23         if(!col[v.fi]) dfs(v.fi,3-c,k);
24         else
25         {
26             if(col[v.fi]==col[u]) f=1;
27         }
28     }
29 }
30 
31 int check(int x)
32 {
33     f=0;
34     memset(col,0,sizeof(col));
35     for(int i=1;i<=n;i++)
36     {
37         if(!col[i]) dfs(i,1,x);
38     }
39     if(f) return 0;
40     else return 1;
41 }
42 
43 
44 
45 int main()
46 {
47     ios::sync_with_stdio(0);
48     cin.tie(0);
49     cin>>n>>m;
50     for(int i=1;i<=m;i++)
51     {
52         int u,v,w;
53         cin>>u>>v>>w;
54         E[u].pb({v,w});
55         E[v].pb({u,w});
56     }
57     int l=0,r=1e9;
58     while(l<r)
59     {
60         int mid=(l+r)/2;
61         if(check(mid)) r=mid;
62         else l=mid+1;
63     }
64     cout<'\n';
65 
66 
67 
68 
69 }

题目二   匈牙利算法

题目链接：https://www.acwing.com/problem/content/374/

思路：对于坐标 x y的格子 如果x+y为奇数， 划分为二分图左边，偶数划分为二分图右边

然后每个点可以从上下左右4个方向有一条边，代表一个可以匹配的点，然后二分图匹配即可

这样就可以转换，等价于每条边不能有公共点

 1 #include
 2 using namespace std;
 3 const int maxn=1e2+10;
 4 const int mod=998244353;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pb push_back
 8 #define pi pair
 9 #define fi first
10 #define sc second
11 
12 int n,t;
13 int g[maxn][maxn];
14 int st[maxn][maxn];
15 pi match[maxn][maxn];
16 
17 int xx[4]={0,0,1,-1};
18 int yy[4]={1,-1,0,0};
19 
20 int dfs(int x,int y)
21 {
22     for(int i=0;i<4;i++)
23     {
24         int tx=xx[i]+x;
25         int ty=yy[i]+y;
26         if(tx<1||ty<1||tx>n||ty>n||g[tx][ty]||st[tx][ty]) continue;
27         st[tx][ty]=1;
28 
29         int &qx=match[tx][ty].fi,&qy=match[tx][ty].sc;
30         if(!qx||dfs(qx,qy))
31         {
32             qx=x,qy=y;
33             return 1;
34         }
35     }
36     return 0;
37 }
38 
39 int main()
40 {
41     ios::sync_with_stdio(0);
42     cin.tie(0);
43     cin>>n>>t;
44     for(int i=0;i)
45     {
46         int x,y;
47         cin>>x>>y;
48         g[x][y]=1;
49     }
50     int ans=0;
51     for(int i=1;i<=n;i++)
52     {
53         for(int j=1;j<=n;j++)
54         {
55             if((i+j)%2&&!g[i][j])
56             {
57                 memset(st,0,sizeof(st));
58                 if(dfs(i,j)) ans++;
59             }
60         }
61     }
62     cout<'\n';
63 
64 
65 
66 
67 
68 }

题目三  最小点覆盖

题目链接：https://www.acwing.com/problem/content/378/

思路： a[i] 可以连去b[i] 一条有向边， 然后要每个任务都完成，相当于最小点覆盖

注意的是 初始模式是0 所以带0的边可以忽略掉

 1 #include
 2 using namespace std;
 3 const int maxn=1e2+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define pi pair
 7 #define fi first
 8 #define sc second
 9 #define pb push_back
10 
11 vector<int>E[maxn];
12 int match[maxn],st[maxn];
13 int n,m,k;
14 
15 
16 int dfs(int u)
17 {
18     for(auto &v:E[u])
19     {
20         if(st[v]) continue;
21         st[v]=1;
22         if(!match[v]||dfs(match[v]))
23         {
24             match[v]=u;
25             return 1;
26         }
27     }
28     return 0;
29 }
30 
31 
32 
33 int main()
34 {
35     ios::sync_with_stdio(0);
36     cin.tie(0);
37     while(cin>>n,n)
38     {
39         cin>>m>>k;
40         for(int i=0;i<=n;i++) E[i].clear();
41         memset(match,0,sizeof(match));
42         for(int i=0;i)
43         {
44             int x,y,z;
45             cin>>x>>y>>z;
46             if(!y||!z) continue;
47             E[y].pb(z);
48         }
49         int ans=0;
50         for(int i=1;i)
51         {
52             memset(st,0,sizeof(st));
53             if(dfs(i)) ans++;
54         }
55         cout<'\n';
56     }
57 
58 
59 
60 
61 
62 }

题目四  最大独立集

题目链接：https://www.acwing.com/problem/content/description/380/

思路：根据格子的下标之和奇偶来划分，每次跳增加的坐标和为3即奇数

所以每次跳跃都会改变奇偶性，所以我们把坐标和奇偶性不同的格子连一条边

然后就成了一张二分图，然后用最大独立集结论  ans= n*m-t-res 

 1 #include
 2 using namespace std;
 3 const int maxn=1e2+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define pi pair
 7 #define fi first
 8 #define sc second
 9 #define pb push_back
10 
11 int n,m,t;
12 int g[maxn][maxn];
13 pi match[maxn][maxn];
14 int st[maxn][maxn];
15 
16 int xx[8]={-1,-2,-2,-1,1,2,2,1};
17 int yy[8]={-2,-1,1,2,-2,-1,1,2};
18 
19 
20 int dfs(int x,int y)
21 {
22     for(int i=0;i<8;i++)
23     {
24         int tx=xx[i]+x;
25         int ty=yy[i]+y;
26         if(tx<1||tx>n||ty<1||ty>m||g[tx][ty]||st[tx][ty]) continue;
27         st[tx][ty]=1;
28         pi tmp=match[tx][ty];
29         if(!tmp.fi||dfs(tmp.fi,tmp.sc))
30         {
31             match[tx][ty]={x,y};
32             return 1;
33         }
34     }
35     return 0;
36 }
37 
38 
39 
40 
41 int main()
42 {
43     ios::sync_with_stdio(0);
44     cin.tie(0);
45     cin>>n>>m>>t;
46     for(int i=1;i<=t;i++)
47     {
48         int x,y;
49         cin>>x>>y;
50         g[x][y]=1;
51     }
52     int ans=0;
53     for(int i=1;i<=n;i++)
54     {
55         for(int j=1;j<=m;j++)
56         {
57             if((i+j)%2&&!g[i][j])
58             {
59                 memset(st,0,sizeof(st));
60                 if(dfs(i,j)) ans++;
61             }
62         }
63     }
64     cout<'\n';
65 
66 
67 
68 
69 }