本文共 1773 字，大约阅读时间需要 5 分钟。

$首先是个最小割模型$

$s向节点连一条选文科的价值(s表示文科)$

$节点向t连一条选理科的价值(t表示理科)$

$这样能满足选理科就割掉文科,选文科就割掉理科$

$但是还有组合情况呢！！设文科组合价值l,理科组合价值r$

$A和B同时选理科就要割掉l$

$A和B同时选文科就要割掉r$

$A和B一个文一个理,就要割掉l和r$

转化为模型来说,需要满足

$当割掉A和B连向t的边表示都选理科,那么还需要割掉r才行$

$换而言之,因为边r的存在,A和B仍然能到t,没有形成割$

$所以新建一个虚点q,A和B向q连inf边,q向t连r边$

这样就没有形成割了!!

点$w$的建立同理

而且当你建立$q$和$w$时,你发现三个条件都满足了

所以模型长这个样子

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #define FOR(i,a,b) for(int i=a;i<=b;++i)const int N=1e5+5,M=5e6+5;const int inf=1<<30;int n,m,tot=1,lnk[N],ter[M],nxt[M],val[M],dep[N],cnr[N];int id(int x,int y) {	return (x-1)*m+y;}void add(int u,int v,int w) {	ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;}void addedge(int u,int v,int w) {	add(u,v,w),add(v,u,0);}int bfs(int s,int t) {	memset(dep,0,sizeof(dep));	memcpy(cnr,lnk,sizeof(lnk));	std::queue
       
         q;	q.push(s),dep[s]=1;	while(!q.empty()) {		int u=q.front(); q.pop();		for(int i=lnk[u];i;i=nxt[i]) {			int v=ter[i];			if(val[i]&&!dep[v]) q.push(v),dep[v]=dep[u]+1;		}	}	return dep[t];}int dfs(int u,int t,int flow) {	if(u==t) return flow;	int ans=0;	for(int i=cnr[u];i&&ans
       
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/108265758 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！