Atcoder TUPC 2023（東北大学プログラミングコンテスト 2023）P. Sub Brackets（dinic 二分图最大独立集）

题目

长为n(n<=500)的尚未确定的括号串，m(m<=500)个限制条件

第i个限制条件形如区间[li,ri]，保证区间长度为偶数，

定下来括号串，满足最多的限制数，使得每个限制对应的区间是一个合法的括号串

输出能满足的最多的限制数

思路来源

官方题解

题解

不合法的情况：

li和lj奇偶性不同，li<lj<=ri<rj

考虑把(看成+1，)看成-1，x[i]为括号串的前缀和数组，

出现这种情况时，要求x[li-1]<=x[lj-1]<=x[ri]且x[li-1]=x[ri]，

有x[lj-1]=x[li-1]，与奇偶性相同矛盾

所以，出现一种冲突时，就将这两个限制条件连一条边，表示不能同时取

剩下的一定可以取，构造方法：

需要取的位置，如果存在要取的li，就放左括号，如果存在要取的ri，就放右括号

否则，如果上一个字符是左括号，则当前是右括号，上一个字符是右括号，则当前是左括号

即贪心把剩下的位置的前缀和降得尽可能低，即可构造出

也可以考虑先把l都为奇数的放入，再放入l为偶数的，

因为任意两个都不严格相交，只会存在内部包含的情况，所以没有冲突

连边之后，二分图最大独立集=m-二分图最大匹配

跑dinic即可，复杂度O(m^2.5)

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map> 
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=505;
const int maxm=8*maxn*maxn;
int level[maxn];
int head[maxn],cnt;
int t,n,m,l[maxn],r[maxn];
int ss,ee;
struct edge{int v,nex;ll w;}e[maxm];
void init()
{
	cnt=0;
	memset(head,-1,sizeof head);
}
void add(int u,int v,ll w)
{
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].nex=head[u];
	head[u]=cnt++;
}
void add2(int u,int v,ll w,bool op)//是否为有向图 
{
	add(u,v,w);
	add(v,u,op?0:w);
}
bool bfs(int s,int t)
{
	queue<int>q;
	memset(level,0,sizeof level);
	level[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		if(x==t)return 1;
		for(int u=head[x];~u;u=e[u].nex)
		{
			int v=e[u].v;ll w=e[u].w;
			if(!level[v]&&w)
			{
				level[v]=level[x]+1;
				q.push(v);
			}
		}
	}
	return 0;
}
ll dfs(int u,ll maxf,int t)
{
	if(u==t)return maxf;
	ll ret=0;
	for(int i=head[u];~i;i=e[i].nex)
	{
		int v=e[i].v;ll w=e[i].w;
		if(level[u]+1==level[v]&&w)
		{
			ll MIN=min(maxf-ret,w);
			w=dfs(v,MIN,t);
			e[i].w-=w;
			e[i^1].w+=w;
			ret+=w;
			if(ret==maxf)break;
		}
	}
	if(!ret)level[u]=-1;//优化,防止重搜,说明u这一路不可能有流量了 
	return ret;
}
ll Dinic(int s,int t)
{
	ll ans=0;
	while(bfs(s,t))
	ans+=dfs(s,INF,t);
	return ans;
}
int main(){ 
    init();
    scanf("%d%d",&n,&m);
    ss=m+1,ee=m+2;
    for(int j=1;j<=m;++j){
        scanf("%d%d",&l[j],&r[j]);
        if(l[j]&1)add2(ss,j,1,1);
        else add2(j,ee,1,1);
    }
    for(int j=1;j<=m;++j){
        for(int k=1;k<=m;++k){
            int x=l[j]&1,y=l[k]&1;
            if(x!=y && l[j]<l[k] && l[k]<=r[j] && r[j]<r[k]){
                if(x)add2(j,k,INF,1);
                else add2(k,j,INF,1);
            }
        }
    }
    printf("%lld\n",m-Dinic(ss,ee));
	return 0;
}