CF884F - Anti-Palindromize

我们发现这个题的数据范围、“字符和位置匹配”再加上一条奇怪的限制，长得就很网络流，那么就考虑如何用网络流做。

考虑重新解释一下这个题面，其实就是：给定一个字符集和 \(n\) 个位置进行匹配，其中，字符 \(ch\) 到位置 \(i\) 的边和字符 \(ch\) 到位置 \(n-i+1\) 的边只能选一个。对于一个匹配可能会有边权，具体而言，位置 \(i\) 和字符 \(ch\) 匹配边的权值是 \(b_i\cdot[s_i=ch]\)。求一个最大权值的匹配。

我们已经将题意转化成很贴近费用流的样子了，唯一的问题在于“字符 \(ch\) 到 \(i\) 的边和字符 \(ch\) 到 \(n-i+1\) 的边只能选一个”很难搞。

考虑增加一组点用于限制，限制点 \((ch,i)(i\le \dfrac{n}{2})\) 是一个从 \(ch\) 连到 \(i\) 和 \(n-i+1\) 必须经过的点。而从 \(ch\) 到 \(i\) 和 \(n-i+1\) 最多有一个流量，所以点 \(ch\) 到 \((ch,i)\) 的流量是 \(1\)，就解决了两条边只能选一个的问题。再从 \((ch,i)\) 连到 \(i\) 和 \(n-i+1\)，边权还是一样计算，唯一的不同就是 \(ch\) 出发的流量只能到达 \(i\) 和 \(n-i+1\) 其中之一。

我们就得到了一个最大费用最大流的问题，把边权设成负的就变成普通的费用流。设 \(\sigma=26\)，点数是 \(2+\sigma+n+\dfrac{\sigma n}{2}\)，边数是 \(\sigma+n+\dfrac{3\sigma n}{2}\)，流量是 \(n\)，总的复杂度是 \(O(\sigma^2n^3)\)，但是网络流一般跑不满，实际表现只跑了 31ms 。

//因为本人的习惯，费用流是封的板子，解释一下主函数中调用的部分：

//Juc::ptt(i)是在图中加上编号为i的点

//Juc::add(a,b,c,d)是在图中加上从a到b，流量为c，费用为d的边和反向边

//Juc::s是源点

//Juc::t是汇点

//Juc::MCMF()是跑费用流

//Juc::cost是运行出来的费用

#define rd(i,n) for(int i=0;i<n;i++)

#define rp(i,n) for(int i=1;i<=n;i++)

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define per(i,a,b) for(int i=b;i>=a;i--)

#define st string

#define vt vector

#define pb push_back

typedef long long ll;

namespace Juc{

	int n,m,s,t,a,b,c,d;

	vt<int>pnts;

	int dep[200005],vis[200005],cur[200005],dist[200005],vist[200005];

	struct edge{

		int a,b,f,c;

		edge(int _a,int _b,int _f,int _c){

			a=_a,b=_b,f=_f,c=_c;

		};

	};

	vt<edge>ve;

	vt<int>vv[200005];

	inline void add(int a,int b,int c,int d){

		ve.pb(edge(a,b,c,d));

		ve.pb(edge(b,a,0,-d));

		vv[a].pb(ve.size()-2);

		vv[b].pb(ve.size()-1);

	}

	inline void ptt(int a){

		pnts.pb(a);

	}

	inline bool SPFA(){

		for(auto i:pnts)dist[i]=1e9,vist[i]=0,vis[i]=0,cur[i]=0;

		queue<int>q;

		q.push(s),vist[s]=1,dist[s]=0;

		while(q.size()){

			int i=q.front();

			q.pop();

			vist[i]=0;

			for(auto g:vv[i]){

				auto &e=ve[g];

				if(e.f&&dist[i]+e.c<dist[e.b]){

					dist[e.b]=dist[i]+e.c;

					if(!vist[e.b]){

						vist[e.b]=1;

						q.push(e.b);

					}

				}

			}

		}

		return dist[t]!=1e9;

	}

	int cost=0;

	inline int DFS(int i,int f){

		if(i==t||f==0)return f;

		vis[i]=1;

		int res=0;

		for(int j=cur[i];j<vv[i].size();j++){

			edge& e=ve[vv[i][j]];

			cur[i]=j;

			if(!vis[e.b]&&dist[e.b]==dist[i]+e.c&&e.f){

				ll flow=DFS(e.b,min(e.f,f));

				ve[vv[i][j]].f-=flow,ve[vv[i][j]^1].f+=flow;

				f-=flow,res+=flow;

				cost+=flow*e.c;

			}

			if(!f)break;

		}

		vis[i]=0;

		return res;

	}

	inline int MCMF(){

		int ans=0;

		while(SPFA()){

			ans+=DFS(s,1e9);

		}

		return ans;

	}

}

int n,b[105],cnt[26];

st s;

signed main(){

	ios::sync_with_stdio(false);

	cin.tie(0);cout.tie(0);

	cin>>n>>s;s='$'+s;

	rp(i,n)cin>>b[i];

	rp(i,n)cnt[s[i]-'a']++;

    //建立源点

	Juc::ptt(0);Juc::s=0;

    //建立字符点和初始流量

	rd(i,26)Juc::ptt(i+1),Juc::add(0,i+1,cnt[i],0);

    //建立位置点

	rp(i,n)Juc::ptt(26+i);

    //建立限制点

	rp(i,n/2)rd(j,26){

		int cur=26+n+(i-1)*26+j+1;

		Juc::ptt(cur);

       //通过流量为1进行限制

		Juc::add(j+1,cur,1,0);

       //连贡献边

		Juc::add(cur,26+i,1,-b[i]*(j+'a'==s[i]));

		Juc::add(cur,26+n-i+1,1,-b[n-i+1]*(j+'a'==s[n-i+1]));

	}

    //建立汇点和最终流量

	int tot=26+n+n*26+1;

	Juc::t=tot;Juc::ptt(tot);

	rp(i,n)Juc::add(26+i,tot,1,0);

	Juc::MCMF();

	cout<<-Juc::cost<<endl;

	return 0;

}

//Crayan_r

巴特西

CF884F - Anti-Palindromize

最新文章

热门文章