杭州网站建设网络公司,中企动力科技股份有限责任公司,云南百度小程序开发,wordpress点赞插件文章目录题目描述解析代码题目描述 在一个n*n的矩阵中#xff0c;有 k个格子中有杂物#xff0c;现在你有一种能力#xff0c;一次可以消除一行或一列格子中的杂物#xff0c;问你至少需要几次可以将这些杂物全部消完。 解析
看起来像是网络流#xff0c;结果竟然是二分图…
文章目录题目描述解析代码题目描述 在一个n*n的矩阵中有 k个格子中有杂物现在你有一种能力一次可以消除一行或一列格子中的杂物问你至少需要几次可以将这些杂物全部消完。 解析
看起来像是网络流结果竟然是二分图。。。 本题关键是模型的转化思路有了后就变成板子了 考虑做法 对于每一个点(x,y)(x,y)(x,y)都连一条从x到y的边最后求最大匹配就是答案 为什么是这样 首先这样连边之后每个点对应一条边因此每条边至少要有一个点被选到因此相当与求这个图的最小点覆盖 然后就是两个很妙的结论 1.最小点覆盖n-最大独立集 2.最大独立集n-最大匹配 为什么? 网上没有找到证明只好自力更生了qwq 首先关于性质1比较简单对于任何一个点独立集SSS它的补集S′SS′都是一个合法的点覆盖因为根据独立集的定义不存在一条边的两个端点都在SSS中那么要使点覆盖最小就要使独立集最大
对于性质2设全集为M最大匹配的点集为P最大独立集的点集为S规定一个点集X的大小用|X|表示 那么最大匹配就是∣P∣/2|P|/2∣P∣/2 我们考虑分为两步证明∣S∣∣M∣−∣P∣/2|S||M|-|P|/2∣S∣∣M∣−∣P∣/2 和 ∣S∣∣M∣−∣P∣/2|S||M|-|P|/2∣S∣∣M∣−∣P∣/2
∣S∣∣M∣−∣P∣/2|S||M|-|P|/2∣S∣∣M∣−∣P∣/2 比较显然考虑在匹配中的每一对点至少有一个点不在独立集中因为它们互相连接所以独立集的大小一定不会超过∣M∣−∣P∣/2|M|-|P|/2∣M∣−∣P∣/2∣S∣∣M∣−∣P∣/2|S||M|-|P|/2∣S∣∣M∣−∣P∣/2 设最大匹配的补集为P′PP′那么首先P‘的所有点可以加入S否则它们就可以匹配了然后对于P中的每一对匹配点A、B考虑它们一定不能同时与P′PP′中的点有连边否则就可以增广了不是最大匹配所以它们中至少一个可以加入SSS中。
证毕
有了上面的分析后本题就变成了一个求最大匹配的板子了
代码
#includebits/stdc.h
using namespace std;
const int N2e6100;
#define ll long long
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();};while(isdigit(c)){xx*10c-0;cgetchar();};return x*f;
}
int n,m;
struct node{int to,nxt;
}p[N1];
int fi[N],cnt-1;
void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;
}
int mat[N],vis[N];
bool hungry(int x,int tim){if(vis[x]tim) return false;vis[x]tim;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(!mat[to]||dfs(mat[to],tim)){mat[to]x;return true;}}return false;
}
int main(){memset(fi,-1,sizeof(fi));nread();mread();for(int i1;im;i){int xread(),yread();addline(x,y);}int res0;for(int i1;in;i){if(dfs(i,i)) res;}printf(%d\n,res);return 0;
}
/*
3 4
1 1
1 3
2 2
3 2
*/
