1.关押罪犯(二分+染色法)
二分罪犯的冲突事件的影响力，二分的条件是大于mid的罪犯的怒气值放在不同的监狱，然后用染色法，假如没冲突就，缩小mid
#include<bits/stdc++.h> using namespace std; const int N=20010,M=200010; int n,m; int h[N],e[M],ne[M],idx,w[M]; int color[N];//0表示还没颜色，1表示染黑色，2表示白色 void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool dfs(int u,int c,int mid)//染到u这个点，目前颜色为c,二分值为mid { color[u]=c;//让这个点颜色为c for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(w[i]<=mid) continue;//假如小于就不用处理了 if(color[j])//假如有颜色了 { if(color[j]==c) return false; //假如颜色相同的话，则不符合 } else if(!dfs(j,3-c,mid)) return false;//3-c就是给j这个点然另一种颜色 } return true; } bool check(int mid) { memset(color,0,sizeof color);//清空 for(int i=1;i<=n;i++) if(!color[i])//假如没有被染色过 if(!dfs(i,1,mid)) return false;//假如染色后不成立 return true; } int main() { cin>>n>>m; memset(h,-1,sizeof h); while(m--) { int a,b,c; cin>>a>>b>>c; add(a,b,c),add(b,a,c); } int l=0,r=1e9; while(l<r)//二分查找最小冲突事件的影响力 { int mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid+1; } cout<<r<<endl; return 0; }
增广路径：从非匹配点走然后非匹配边然后匹配边然后非匹配然后匹配....最后是非匹配点
最大匹配等价于不存在增广路径
2.棋盘覆盖（最大匹配数）
#include<bits/stdc++.h> #define x first #define y second using namespace std; typedef pair<int,int> pii; const int N=110; pii match[N][N]; bool st[N][N],g[N][N]; int n,m,res=0; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; bool find(int x,int y)//帮x,y这个点找对象 { for(int i=0;i<4;i++)//枚举他可能的对象 { int a=x+dx[i],b=y+dy[i]; if(a<1||a>n||b<1||b>n) continue;//假如越界 if(st[a][b]||g[a][b]) continue;//假如这个点有其他的对象 st[a][b]=true;//先标记这个点有对象了 pii t=match[a][b]; if(t.x==0||find(t.x,t.y))//假如这个点还没对象或者这个点有对象，但是可以让给别人 { match[a][b]={x,y};//则把a,b给x,y return true; } } return false;//反之没对象 } int main() { cin>>n>>m; while(m--) { int a,b; cin>>a>>b; g[a][b]=true; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if((i+j)&1&&!g[i][j])//枚举奇数的情况 { memset(st,0,sizeof st); //清空上一层的状态 if(find(i,j)) res++;//假如这个点找的到对象，则答案++ } cout<<res<<endl; return 0; }
最小点覆盖：每条边至少选出一个点，使得选出的点最小就是最小点覆盖
最小点覆盖 等于 最大匹配数
3.机器任务（最小点覆盖）
这题ai与bi可以看成ai->bi，然后答案就是选最少的点使得所有边都覆盖了，其实就是最小点覆盖问题，就是求最大匹配数即可
#include<bits/stdc++.h> using namespace std; const int N=110; bool g[N][N],st[N]; int match[N]; int n,m,k; bool find(int u)//帮u找女朋友 { for(int i=1;i<m;i++)//枚举可能的女朋友 if(!st[i]&&g[u][i])//假如这个女朋友没有男朋友并且我跟他有关系 { st[i]=true;//标记这个点有男朋友了 int t=match[i];//找一下这个点的男朋友 if(t==0||find(t))//假如没男朋友或者她男朋友可以换个女朋友 { match[i]=u;//则让她的男朋友是我 return true;//返回找到了 } } return false;//反之没女朋友 } int main() { while(cin>>n,n) { memset(g,0,sizeof g);//清空 memset(match,0,sizeof match);//清空 cin>>m>>k; while(k--) { int t,a,b; cin>>t>>a>>b; g[a][b]=true;//从a->b连条边 } int res=0; for(int i=1;i<n;i++) { memset(st,0,sizeof st);//清空 if(find(i)) res++;//假如匹配成功 } cout<<res<<endl; } return 0; }
最大独立集：一个图中，选出最多的点，使得选出的点内部没有边
最大团：一个图中，选出最多的点，使得选出的点任意两点都有边
最大独立集与最大团互补
最大独立集等价于在原图中破环最少的点，将所有边都破坏掉
等价于 找最小点覆盖 等价于 找最大匹配
4.骑士放置（最大独立集）
把所有可以攻击到的马连条边，则答案就是求两两不能攻击到的马，也即最大独立集的问题
把奇数和偶数分别为两个集合，也即符合二分图，然后八个方向攻击到的格子都与自己的格子的奇偶性不同，所有可以用二分图最大独立集来求解
答案就是n*m-k-最大匹配数
#include<bits/stdc++.h> #define x first #define y second using namespace std; typedef pair<int,int> pii; const int N=110; bool g[N][N],st[N][N]; pii match[N][N]; int n,m,k; int dx[8]={-2,-1,1,2,2,1,-1,-2},dy[8]={1,2,2,1,-1,-2,-2,-1};//八个方向 bool find(int x,int y) { for(int i=0;i<8;i++)//枚举可能的女朋友 { int a=x+dx[i],b=y+dy[i]; if(a<1||a>n||b<1||b>m) continue;//假如越界 if(st[a][b]||g[a][b]) continue;//假如已经有男朋友了，或者是坏格子 st[a][b]=true;//标记这个点已经有男朋友了 pii t=match[a][b]; if(t.x==0||find(t.x,t.y))//假如没有男朋友或者这个男的可以换个女朋友 { match[a][b]={x,y};//就把这个女的抢过来给我 return true;//返回有女朋友 } } return false;//反之没 } int main() { cin>>n>>m>>k; for(int i=1;i<=k;i++)//标记所有坏的格子 { int a,b; cin>>a>>b; g[a][b]=true; } int res=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!g[i][j]&&(i+j)&1)//假如是奇数和不是坏格子 { memset(st,0,sizeof st);//清空 if(find(i,j)) res++;//假如找的到女朋友 } cout<<n*m-k-res<<endl;//输出最大独立集 return 0; }
最小路径点覆盖： 对于一个有向无环图（DAG），用最少的互不相交的路径将所有点覆盖
最小路径重复点覆盖：求一遍原图的传递闭包，再求一遍最小路径点覆盖则就是
5.捉迷藏（最小路径重复点覆盖）
题目就是从任意一个点出发，都不能走到另外一个点，答案就是n-最小路径重复点覆盖
#include<bits/stdc++.h> using namespace std; const int N=210; bool g[N][N],st[N]; int match[N]; int n,m; bool find(int x)//帮x找女朋友 { for(int i=1;i<=n;i++)//枚举可能的女朋友 if(!st[i]&&g[x][i])//假如这个女的没男朋友并且我跟他有关系 { st[i]=true;//标记这个女的找到了男朋友 int t=match[i]; if(t==0||find(t))//假如这个女的没男朋友或着那男的可以换个女朋友 { match[i]=x;//则把这个女的让给我 return true;//返回找到了 } } return false;//反之找不到 } int main() { cin>>n>>m; while(m--) { int a,b; cin>>a>>b; g[a][b]=true; } //做一遍传递闭包 for(int k=1;k<=n;k++)//floryd求传递闭包 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]|=g[i][k]&g[k][j]; int res=0; for(int i=1;i<=n;i++) { memset(st,0,sizeof st);//清空 if(find(i)) res++;//假如找的到女朋友 } cout<<n-res<<endl;//输出最大路径重复点覆盖 return 0; }
