图论专题班二分图例题与练习

图论专题班二分图例题与练习 图论专题班二分图例题与练习

文章目录

图论专题班二分图例题与练习

课程内容

二分图的最大匹配Konig定理——最小点覆盖数等于最大匹配最小路径覆盖 Graph Coloring I[ZJOI2009]假期的宿舍[ZJOI2007]矩阵游戏棋盘覆盖Antenna PlacementGeorge and Interesting GraphPlug It In 网络流(转化为网络流解决二分图问题)

Going HomeAsteroids

课程内容 二分图的最大匹配

匈牙利算法 O ( n m ) O(nm) O(nm)

//函数体
bool find(int x){
    for(int i = h[x];~i;i=ne[i]){
        int y = e[i];
        if(!st[y]){
            st[y] = true;
            // y没有匹配或者匹配的能够换人。
            if(!match[y] || find(match[y])){
                match[y] = x;
                return true;
            }
        }
    }
    return false;
}


//调用
    for(int i = 1;i<=n1;i++){
        memset(st,0,sizeof st);
        find(i);
    }

Konig定理——最小点覆盖数等于最大匹配

最小点覆盖：假如选了一个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖所有的边。

最小路径覆盖

通俗点将，就是在一个有向图中，找出最少的路径，使得这些路径经过了所有的点。
最 小 路 径 覆 盖 = 总 顶 点 数 − 最 大 匹 配 最小路径覆盖 =总顶点数 - 最大匹配 最小路径覆盖=总顶点数−最大匹配

Graph Coloring I

深度搜索
重色必有环。

代 码 代码 代码

#include
#include
#include
using namespace std;
const int N = 3e5+10;
int h[N],ne[N<<1],e[N<<1],idx;
int color[N];
int n,m;
vector vec;
int begins = -1;
void add(int a,int b){
    ne[idx] = h[a] , e[idx] = b , h[a] = idx++;
}
void dfs(int x,int col){
    color[x] = col;
    for(int i = h[x];i!=-1;i=ne[i]){
        int y = e[i];
        //相等说明有环。
        if(color[x] == color[y]){
            vec.push_back(x);
            begins = y;
            return ;
        }
        else if(color[y] == -1)dfs(y,1-color[x]);
        //环头
        if(begins == x){
            vec.push_back(x);
            begins = -1;
            return ;
        }
        //
        if(begins != -1){
            vec.push_back(x);
            return ;
        }
        if(vec.size()!=0)return ;
    }
}
int main(){
    cin >> n >> m;
    memset(h,-1,sizeof h);
    for(int i = 1;i<=m;i++){
        int x,y;
        cin >> x >> y;
        add(x,y),add(y,x);
    }
    memset(color,-1,sizeof color);
    for(int i = 1;i<=n;i++){
        if(color[i]==-1){
            dfs(i,0);
        }
        //有环
        if(vec.size()!=0)break;
    }
    if(vec.size()!=0){
        cout << vec.size() << endl;
        for(int i = 0;i 
[ZJOI2009]假期的宿舍 
 
 
题目：
 学校放假了······有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如A和B都是学校的学生，A要回家，而C来看B，C与A不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是B睡A的床而C睡B的床。
 而实际情况可能非常复杂，有的人可能认识好多在校学生，在校学生之间也不一定都互相认识。我们已知一共有n个人，并且知道其中每个人是不是本校学生，也知道每个本校学生是否回家。
 问是否存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住。
 
 
 
 
输入描述:
 第一行一个数T表示数据组数。接下来T组数据，
 每组数据第一行一个数n表示涉及到的总人数。
 接下来一行n个数，第i个数表示第i个人是否是在校学生(0表示不是，1表示是)。
 再接下来一行n个数，第i个数表示第i个人是否回家
 (0表示不回家，1表示回家，注意如果第i个人不是在校学生，那么这个位置上的数是一个随机的数，
 你应该在读入以后忽略它)。
 接下来n行每行n个数，
 第i行第j个数表示i和j是否认识
 (1表示认识，0表示不认识，第i行i个的值为0，但是显然自己还是可以睡自己的床)，
 认识的关系是相互的。
 1 ≤ n ≤ 50,1 ≤ T ≤ 20
 
 
 
 
输出描述:
 对于每组数据，如果存在一个方案则输出“_”(不含引号)否则输出“T_T”(不含引号)。
 (注意输出的都是半角字符，即三个符号的ASCII码分别为94,84,95)
 
 
 
 
建图：
 
 
 

    
     
      
       
        代
       
       
        码
       
      
      
       代码
      
     
    代码
 
#include
#include
#include
#include
#include
//526526
using namespace std;
const int N= 300;
int h[N],ne[N<<2],e[N<<2],idx;

int n;
int match[N];
bool st[N];
int atshool[N],gohome[N];
int delat = 110;
vector vec;
void add(int a,int b){
   ne[idx] = h[a] , e[idx] = b,h[a] = idx++;
} 
bool find(int x){
   for(int i = h[x];~i;i=ne[i]){
   	int y = e[i];
   	if(!st[y]){
   		st[y] = true;
   		if(!match[y] || find(match[y])){
   			match[y] = x;
   			return true;
   		}
   	}	
   }
   return false;
}
int main(){
   int t;
   cin >> t;
   while(t--){
   	memset(h,-1,sizeof h);
   	memset(match,0,sizeof match);
       vec.clear();
   	cin >> n;
   	for(int i = 1;i<=n;i++){
   		cin >> atshool[i];
   		if(!atshool[i])vec.push_back(i);
   	}
   	for(int i = 1;i<=n;i++){
   		cin >> gohome[i];
   		if(!gohome[i] && atshool[i]){
   			vec.push_back(i);
   			add(i,i+delat);
   		}
   	}
   	for(int i = 1;i<=n;i++){
   		for(int j = 1;j<=n;j++){
   			int k ;
   			cin >> k; 
   			// 建边原则 非在校生--> 在校生 ，不回家在校生 --> 在校生 
   			if( k == 1 && ((!atshool[i] && atshool[j]) || (atshool[i] && !gohome[i] && atshool[j])) )add(i,j + delat);
   		}
   	}
   	int res = 0;
   	for(int i = 0;i 
[ZJOI2007]矩阵游戏 
 
 
小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N *N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。
 每次可以对该矩阵进行两种 *** 作：
 行交换 *** 作：选择 矩阵的任意两行，交换这两行（即交换对应格子的颜色）
 列交换 *** 作：选择矩阵的任意行列，交换这两列（即交换 对应格子的颜色）
 游戏的目标，即通过若干次 *** 作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑 色。
 对于某些关卡，小Q百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！！于是小Q决定写一个程序来判断这些关卡是否有解。
 
 
 
 
输入描述:
 第一行包含一个整数T，表示数据的组数。
 接下来包含T组数据，每组数据第一行为一个整数N，表示方阵的大小；
 接下来N行为一个N*N的01矩阵（0表示白色，1表示黑色）。
 
 
 
 
输出描述:
 输出文件应包含T行。
 对于每一组数据，如果该关卡有解，输出一行Yes；否则输出一行No。
 
 
 
 
建图：
 行和列为点，黑点为边，二分图匹配，如果对于没各行都能找到一个列，即可行
 原因 ：对于最后的匹配不同x一定对应不同y，找到两个点(x1,y2) (x2,y2)交换肯定能交换到对角线。
 
 

    
     
      
       
        代
       
       
        码
       
      
      
       代码
      
     
    代码
 
#include
#include
#include
#include
//526526
using namespace std;
const int N = 40100;
int h[N],e[N],ne[N],idx;
int n;
int delat = 200;
int match[N];
bool st[N];
void add(int a,int b){
	ne[idx] = h[a],e[idx] = b,h[a] =  idx++;
}
bool find(int x){
	for(int i = h[x];~i;i=ne[i]){
		int y = e[i];
		if(!st[y]){
			st[y] = true;
			if(!match[y] || find(match[y])){
				match[y] = x;
				return true;
			}
		}		
	}
	return false;
}
int main(){
	int t; 
	cin >> t;
	while(t--){
		cin >> n;
		int tp;
        idx = 0;
		memset(h,-1,sizeof h);
		memset(match,0,sizeof match);
		for(int i = 1;i<=n;i++)
			for(int j = 1;j<=n;j++)
			{
				cin >> tp;
				if(tp == 1)add(i,j+delat);
			}
		int res = 0;
		for(int i=1;i<=n;i++){
			memset(st,0,sizeof st);
			if(find(i))res++;
			else break;
		}
		if(res == n)cout <<"Yes"< 
棋盘覆盖 
 
 
给定一个N行N列的棋盘，已知某些格子禁止放置。求最多能往棋盘上放多少块的长度为2、宽度为1的骨牌。骨牌的边界与格线重合(骨牌占用两个格子),并且任意两张骨牌都不重叠。N,M≤100。
 
 
 
 
输入描述:
 第一行为n，m（表示有m个删除的格子）
 第二行到m+1行为x,y，分别表示删除格子所在的位置
 x为第x行
 y为第y列
 
 
 
 
输出描述:
 一个数，即最大覆盖格数
 
 
 
 
思路：
 将棋盘按照国际象棋格子分开（黑白 各一边），相邻的连边，求最大匹配。（。。骨牌也可以竖着放。。）
 
 

    
     
      
       
        代
       
       
        码
       
      
      
       代码
      
     
    代码
 
#include
#include
#include
#include
#include
//526526
using namespace std;
const int N = 2e4+10;
int h[N],ne[N],e[N],idx;
void add(int a,int b){
	ne[idx] = h[a] , e[idx] = b, h[a]=idx++;
}
int n,m;
bool mp[110][110],st[N];
int match[N];
vector vec;
bool find(int x){
	for(int i = h[x];~i;i=ne[i]){
		int y = e[i];
		if(!st[y]){
			st[y] = true;
			if(!match[y] || find(match[y])){
				match[y] = x;
				return true;
			}
		}
	}
	return false;
}
int main(){
	cin >> n >> m ;
    memset(h,-1,sizeof h);
	for(int  i = 1;i<=m;i++){
		int x,y;
		cin >> x >> y;
		mp[x][y] = 1;
	}
	for(int i = 1;i<=n;i++)
		for(int j = 1;j<=n;j++)
		{
			if((i+j)&1 || mp[i][j])continue;
			vec.push_back(i*n+j);
			if(i-1 >= 1 && !mp[i-1][j])add(i*n+j,(i-1)*n+j);
			if(i+1 <= n && !mp[i+1][j])add(i*n+j,(i+1)*n+j);
            if(j-1 >= 1 && !mp[i][j-1])add(i*n+j,i*n+j-1);
            if(j+1 <= n && !mp[i][j+1])add(i*n+j,i*n+j+1);
		}
	int res = 0;
	for(int i = 0;i 
Antenna Placement 
 
 
The Global Aerial Research Centre has been allotted the task of building the fifth generation of mobile phone nets in Sweden. The most striking reason why they got the job, is their discovery of a new, highly noise resistant, antenna. It is called 4DAir, and comes in four types. Each type can only transmit and receive signals in a direction aligned with a (slightly skewed) latitudinal and longitudinal grid, because of the interacting electromagnetic field of the earth. The four types correspond to antennas operating in the directions north, west, south, and east, respectively. Below is an example picture of places of interest, depicted by twelve small rings, and nine 4DAir antennas depicted by ellipses covering them.
 Obviously, it is desirable to use as few antennas as possible, but still provide coverage for each place of interest. We model the problem as follows: Let A be a rectangular matrix describing the surface of Sweden, where an entry of A either is a point of interest, which must be covered by at least one antenna, or empty space. Antennas can only be positioned at an entry in A. When an antenna is placed at row r and column c, this entry is considered covered, but also one of the neighbouring entries (c+1,r),(c,r+1),(c-1,r), or (c,r-1), is covered depending on the type chosen for this particular antenna. What is the least number of antennas for which there exists a placement in A such that all points of interest are covered?
 
 
 
 
输入描述:
 On the first row of input is a single positive integer n, specifying the number of scenarios that follow. Each scenario begins with a row containing two positive integers h and w, with 1 <= h <= 40 and 0 < w <= 10. Thereafter is a matrix presented, describing the points of interest in Sweden in the form of h lines, each containing w characters from the set [’’,‘o’]. A '’-character symbolises a point of interest, whereas a ‘o’-character represents open space.
 
 
 
 
输出描述:
 For each scenario, output the minimum number of antennas necessary to cover all ‘*’-entries in the scenario’s matrix, on a row of its own.
 
 
 
 
思路 ：承接上题 ，求完最大匹配后 剩下的点再去覆盖， 即： 总顶点数 - 2 * 最大匹配数 + 最大匹配数 = 总顶点数 - 最大匹配数 （二分图上表示 ： 用最少的边覆盖全部点）
 
 

    
     
      
       
        代
       
       
        码
       
      
      
       代码
      
     
    代码
 
#include
#include
#include
#include
#include
//526526
using namespace std;
const int N = 2e5+10;
int h[N],ne[N],e[N],idx;
void add(int a,int b){
	ne[idx] = h[a],e[idx] = b,h[a] = idx++;
}
char mp[110][110];
int match[N];
bool st[N];
int n,m,t;
bool find(int x){
	for(int i = h[x];~i;i=ne[i]){
		int y = e[i];
		if(!st[y]){
			st[y] = true;
			if(!match[y] || find(match[y])){
				match[y] = x;
				return true;
			}
		}
	}
	return false;
}
int main(){
	cin >> t;
	while(t--){
		int all = 0;
		vector vec;
		cin >> n >>  m;
		memset(match,0,sizeof match);
		memset(h,-1,sizeof h);
		idx = 0;
		for(int i = 1;i<=n;i++)
			for(int j = 1;j<=m;j++){
				cin >> mp[i][j];
				if(mp[i][j] == '*')all++;
			}
		for(int i = 1;i<=n;i++)
			for(int j = 1;j<=m;j++){
				if( !((i+j)&1) && mp[i][j] == '*'){
					vec.push_back(i*m+j);
					if(i-1 >= 1 && mp[i-1][j] == '*')add(i*m+j,(i-1)*m+j);
					if(i+1 <= n && mp[i+1][j] == '*')add(i*m+j,(i+1)*m+j);
		            if(j-1 >= 1 && mp[i][j-1] == '*')add(i*m+j,i*m+j-1);
		            if(j+1 <= m && mp[i][j+1] == '*')add(i*m+j,i*m+j+1);
				}
			}
		int res = 0;	
		for(int i = 0;i 
George and Interesting Graph 
题目链接
 
 
 
思路：根据题意可构思有趣图(
     
      
       
        
         把
        
        
         中
        
        
         心
        
        
         点
        
        
         去
        
        
         掉
        
        
         剩
        
        
         下
        
        
         的
        
        
         为
        
        
         多
        
        
         个
        
        
         环
        
       
       
        把中心点去掉剩下的为多个环
       
      
     把中心点去掉剩下的为多个环)
 枚举中心点 
     
      
       
        
         u
        
       
       
        u
       
      
     u
 
 
 
  
1.对于
      
       
        
         
          u
         
        
        
         u
        
       
      u,检查边，多减少补
 2.其他顶点不管与中心点的边，对于其他的边多减少补。
 
 
 
 

    
     
      
       
        代
       
       
        码
       
      
      
       代码
      
     
    代码
 
#include
#include
using namespace std;
const int N = 1e4+10;
int h[N<<1],ne[N<<1],e[N<<1],idx;
void add(int a,int b){
    ne[idx] = h[a],e[idx] = b,h[a] = idx++;
}
int n,m;
int mp[510][510];
int delat = 501;
int match[2001];
int st[2001];
int vex ;
bool find(int x){
    for(int i = h[x];~i;i=ne[i]){
        int y = e[i];
        if(vex + delat == y)continue;
        if(!st[y]){
            st[y] = true;
            if(!match[y] || find(match[y])){
                match[y] = x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    cin >> n >> m ;
    memset(h,-1,sizeof h);
    for(int i = 1;i<=m;i++){
        int x ,y;
        scanf("%d%d",&x,&y);
        mp[x][y] = 1;
        add(x,y+delat);
    }
    int res = 0x3f3f3f3f;
    for(int i = 1;i<=n;i++){
    	vex = i;
    	memset(match,0,sizeof match);
        int tp = 0,u = 0;
        for(int j = 1;j<=n;j++){
            if(mp[i][j] == 0)tp  ++;
            else u ++;
            if(i == j)continue;
			if(mp[j][i] == 0)tp ++;
			else u ++;	
		}
        int k = 0;
        for(int j = 1;j<=n;j++){
            if(j == i)continue;
            memset(st,0,sizeof st);
            if(find(j))k++;
        }
       //cout << i << " " << tp << " " << u <<" "<< k << endl;
       // cout << m-u-k+tp+n-1-k << endl;
        res = min(res,m-u-k+tp+n-1-k);
    }
    cout << res << endl;
    return 0;
}


 
Plug It In 
题目链接
 
 
 
题意：有n个插孔，m个机器，和一个插板，一个插孔可以连接一个机器，插板可以使一个插孔连接三个机器，找到最大的连接数。
 
 
 
 
Adam just moved into his new apartment and simply placed everything into it at random. This
 means in particular that he did not put any effort into placing his electronics in a way that each
 one can have its own electric socket.
 Since the cables of his devices have limited reach, not every device can be plugged into every
 socket without moving it first. As he wants to use as many electronic devices as possible right
 away without moving stuff around, he now tries to figure out which device to plug into which
 socket. Luckily the previous owner left behind a plugbar which turns one electric socket into 3.
 Can you help Adam figure out how many devices he can power in total?
 Input
 The input consists of:
 • one line containing three integers m, n and k, where
 – m (1 ≤ m ≤ 1 500) is the number of sockets;
 – n (1 ≤ n ≤ 1 500) is the number of electronic devices;
 – k (0 ≤ k ≤ 75 000) is the number of possible connections from devices to sockets.
 • k lines each containing two integers xi and yi
 indicating that socket xi can be used to
 power device yi
 .
 Sockets as well as electronic devices are numbered starting from 1.
 The plugbar has no cable, i.e. if it is plugged into a socket it simply triples it.
 Output
 Output one line containing the total number of electrical devices Adam can power.
 
 
 
 
思路：先跑一边最大匹配，然后枚举每个插线板（即增加2个点在最大匹配上跑最大匹配）
 
 

    
     
      
       
        代
       
       
        码
       
      
      
       代码
      
     
    代码
 
#include
#include
using namespace std;
const int N = 2e5+10;;
int h[N<<1],ne[N<<1],e[N<<1],idx;
void add(int a,int b){
    ne[idx] = h[a],e[idx] = b,h[a] = idx++;
}
int n,m,k;
int match1[N];
int match2[N];
int st[N];
int delat = 2000,delat2 = 4000, delat3 = 6000;
int find(int x,int *match){
    for(int i = h[x];~i;i=ne[i]){
        int y = e[i];
        if(!st[y]){
            st[y] = true;
            if(!match[y] || find(match[y],match)){
                match[y] = x;
                return y;
            }
        }
    }
    return 0;
}

int main(){
	cin >> n >> m >> k;
	memset(h,-1,sizeof h);
	for(int i = 1;i<=k;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y+delat);
		add(x+delat2,y+delat);
		add(x+delat3,y+delat);
	}
	int res = 0;
	for(int i = 1;i<=n;i++){
		memset(st,0,sizeof st);
		if(find(i,match1))res++;
	}
	int tp = 0,ans = 0;
	for(int i = 1;i<=n;i++){
		memcpy(match2,match1,sizeof match1);
		tp = 0;
		memset(st,0,sizeof st);
		if(find(i+delat2,match2))tp++;
		memset(st,0,sizeof st);
		if(find(i+delat3,match2))tp++;
		ans = max(tp,ans);
		if(tp==2)break;
	}
	cout << ans + res << endl;
	return 0;
}

 
网络流(转化为网络流解决二分图问题) 
 
 
二分图最大匹配可以转换成网络流模型。
 将源点连上左边所有点，右边所有点连上汇点，容量皆为 1 。原来的每条边从左往右连边，容量也皆为1 ，最大流即最大匹配。 如果使用 
     
      
       
        
         D
        
        
         i
        
        
         n
        
        
         i
        
        
         c
        
       
       
        Dinic
       
      
     Dinic 算法 求该网络的最大流，可在 
     
      
       
        
         s
        
        
         q
        
        
         r
        
        
         t
        
        
         (
        
        
         n
        
        
         )
        
        
         ∗
        
        
         m
        
       
       
        sqrt(n) * m
       
      
     sqrt(n)∗m 求出.
 
 
Going Home 
 
 
On a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a $1 travel fee for every step he moves, until he enters a house. The task is complicated with the restriction that each house can accommodate only one little man.
 Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a ‘.’ means an empty space, an ‘H’ represents a house on that point, and am ‘m’ indicates there is a little man on that point.
 You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.
 
 
 
 
输入描述:
 There are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of 'H’s and 'm’s on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.
 
 
 
 
输出描述:
 For each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.
 
 
最小费用流
 
 
 
建图 ：
 
     
      
       
        
         h
        
        
         −
        
        
         −
        
        
         >
        
        
         m
        
       
       
        h --> m
       
      
     h−−>m 权值为距离，流量为1
 
     
      
       
        
         S
        
        
         −
        
        
         −
        
        
         >
        
        
         h
        
       
       
        S --> h
       
      
     S−−>h 权值为0，流量为1
 
     
      
       
        
         m
        
        
         −
        
        
         −
        
        
         >
        
        
         E
        
       
       
        m --> E
       
      
     m−−>E 权值为0，流量为1
 
 

    
     
      
       
        代
       
       
        码
       
      
      
       代码
      
     
    代码
 
#include
#include
#include
#include
#include
using namespace std;
const int N = 300,M = 1e4+10,inf  = 0x3f3f3f3f;
int h[N<<3],ne[M<<3],e[M<<3],idx,f[M<<3],w[M<<3];
char p[N][N];
int pre[M<<3],d[N];
int dist[N];
bool st[N];
int n,m;
int delat = 100;
struct node{
    int x,y;
};
vector posH,posm;
int S = 222,E = 221;
void add(int a,int b,int c,int d){
    ne[idx] = h[a] , e[idx] = b , f[idx] = c,w[idx] = d,h[a] = idx++;
    ne[idx] = h[b] , e[idx] = a , f[idx] = 0,w[idx] = -d,h[b] = idx++;
}
bool spfa(int s,int t){
    for(int i = 0;i q;
    q.push(s);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        st[u] = false;
        for(int i = h[u];~i;i=ne[i]){
            int y = e[i];
            if(f[i] && dist[y] > dist[u] + w[i]){
                dist[y] = dist[u] + w[i];
                d[y] = min(d[u],f[i]);
                pre[y] = i;
                if(!st[y]){
                    q.push(y);
                    st[y] = true;
                }
            }
        }
    }
    return dist[t] != inf;
}
int EK(int s,int t){
    int cost = 0,flow = 0;
    while(spfa(s,t)){
        for(int i = t;i!=s;i=e[pre[i]^1]){
            f[pre[i]] -= d[t];
            f[pre[i]^1] += d[t];
        }
        cost += dist[t];
        flow += d[t];
    }
    return cost;
}
int main(){
    while(cin >> n >> m){
        if(n == 0)return 0;
        memset(h,-1,sizeof h);
        idx = 0;
        posH.clear(),posm.clear();
        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=m;j++){
                cin >> p[i][j];
                if(p[i][j] == 'H')posH.push_back({i,j});
                if(p[i][j] == 'm')posm.push_back({i,j});
            }
        for(int i = 0;i 
Asteroids 
题目链接
 
 
 
作图：
 将列，行当左右点(二分图的左右点集)，陨石位置当边。
 问题转换为最小点覆盖( == 二分图的最大匹配)
 
 
 

    
     
      
       
        代
       
       
        码
       
      
      
       代码
      
     
    代码
 
#include
#include
#include
#include
#include
//526526
using namespace std;
const int N = 510,M = 2e4+10,inf = 0x3f3f3f3f;
int h[M],ne[M],e[M],f[M],idx;
int n,k;
int d[N<<2],pre[N<<2];
void add(int a,int b,int c){
	ne[idx] = h[a],e[idx] = b,f[idx] = c,h[a] = idx++;
	ne[idx] = h[b],e[idx] = a,f[idx] = 0,h[b] = idx++;
}
int EK(int s,int t){
	int flow = 0;
	while(1){
		memset(d,0,sizeof d);	
		queue q;
		q.push(s);
		d[s] = inf;
		while(!q.empty()){
			int u = q.front();
			q.pop();
			for(int i = h[u];~i;i=ne[i]){
				int y = e[i];
				if(!d[y] && f[i] > 0){
					d[y] = min(d[u],f[i]);
					pre[y] = i;
					q.push(y);
				}
			}
			if(d[t])break;
		}
		if(!d[t])break;
		for(int i = t;i!=s;i=e[pre[i]^1]){
			f[pre[i]] -= d[t];
			f[pre[i]^1] += d[t];
		}
		flow += d[t];
	}
	return flow; 
}
int main(){
	int s = 0,t = N*2+1,delat = 500;
	cin >> n >> k;
	memset(h,-1,sizeof h);
	for(int i = 1;i<=k;i++){
		int x,y;
		cin >> x >> y;	
		add(x,y+delat,inf);
	}
	for(int i = 1;i<=n;i++){
		add(s,i,1);
		add(i+delat,t,1);
	}
	cout << EK(s,t) << endl;
	return 0;
}


					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5702961.html