本文主要是介绍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;
}
这篇关于Atcoder TUPC 2023(東北大学プログラミングコンテスト 2023)P. Sub Brackets(dinic 二分图最大独立集)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!