[题解] Atcoder ARC 142 E Pairing Wizards 最小割

题目

建图很妙，不会。

考虑每一对要求合法的巫师(x,y)，他们两个的\(a\)必须都大于\(min(b_x,b_y)\)。所以在输入的时候，如果\(a_x\)或者\(a_y\)小于\(min(b_x,b_y)\)，可以先把\(a_x\)和\(a_y\)提升到\(min(b_x,b_y)\)(以后的a数组都指做过这步操作的)。接下来如果\(max(a_x,a_y)\geq max(b_x,b_y)\)，那么这一对已经符合要求，可以直接不管。接下来只考虑需要管的。

发现每一对需要管的(x,y)，两个巫师中有且仅有一个满足\(a<b\)。因此可以把所有需要管的(x,y)涉及到的巫师分成左右两组，左边的\(a<b\)，右边的\(a \geq b\)。把每一对(x,y)都当成连接x,y的无向边，发现连成了一张二分图。把左边的点称为X类点，右边的称为Y类点。现在我们想让每一个X类点i满足：\(b_i \leq max(a_i,max_{j和i相邻}a_j)\)，容易发现这与原题的要求等价。

提升X类点和Y类点的strength分别有什么用呢？发现提升一个X类点i，只对i自己有用，也就是使得\(a_i \geq b_i\)，因为它的所有相邻的点j都是Y类点，都已经满足了\(a_j\geq b_j\)。提升一个Y类点则可能会帮助满足相邻的X类点的要求

考虑最小割。对每一个X类点i建立一个点\(c_i\)，对于每一个Y类点i和一个[1,100]的整数j建立一个点\(d_{i,j}\)。从源点向每一个\(c_i\)连\(b_i-a_i\)的边，割掉这条边意味着点i的要求靠提升\(a_i\)满足；从每一个\(d_{i,j}向d_{i,j-1}连inf的边\)；每一个\(d_{i,j}\)向汇点连边，\(j\leq a_i\)则流量为0，否则为1。最后，对于每一对(x,y)，从\(c_x\)向\(d_{y,b_x}\)连inf的边。这个图的最小割加上输入的时候提升的值就是答案。

正确性证明：发现对于每条最后一种类型的边，这条边是不会割的，为了保证没有剩余流量，要么\(s \to c_x\)的边被割掉，代表提升\(a_x\)来满足要求；要么割掉\(d_{y,p}(p \leq b_x)\)到t的所有边(根据建图，这些边的代价和为\(b_x-a_y\))，代表\(a_y\)至少为\(b_x\)。证毕。

时间复杂度：O(能过)。

点击查看代码

#include <bits/stdc++.h>

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

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

#define LL long long

#define pii pair <int,int>

#define pb push_back

#define fi first

#define se second

#define mpr make_pair

using namespace std;

struct node

{

	LL to,flow,rev;

	node(LL a,LL b,LL c):to(a),flow(b),rev(c){}

};

namespace maxFlow

{

	LL n,dist[100010],cur[100010];

	vector <node> g[100010];

	queue <LL> q;

	void add_edge(LL x,LL y,LL z)

	{

		g[x].pb(node(y,z,g[y].size()));

		g[y].pb(node(x,0,g[x].size()-1));

	}

	void bfs(LL s)

	{

		rep(i,n+5) dist[i]=-1;

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

		while(!q.empty())

		{

			int f=q.front();q.pop();

			rep(i,g[f].size())

			{

				if(dist[g[f][i].to]!=-1||g[f][i].flow==0) continue;

				dist[g[f][i].to]=dist[f]+1;

				q.push(g[f][i].to);

			}

		}

	}

	LL dfs(LL pos,LL t,LL flow)

	{

		if(pos==t) return flow;

		for(int i=cur[pos];i<g[pos].size();++i,++cur[pos])

		{

			if(g[pos][i].flow==0||dist[g[pos][i].to]!=dist[pos]+1) continue;

			LL flow2=dfs(g[pos][i].to,t,min(flow,g[pos][i].flow));

			if(flow2>0)

			{

				g[pos][i].flow-=flow2;

				g[g[pos][i].to][g[pos][i].rev].flow+=flow2;

				return flow2;

			}

		}

		return 0;

	}

	LL max_flow(LL s,LL t)

	{

		LL ret=0;

		while(true)

		{

			bfs(s);

			if(dist[t]==-1) return ret;

			rep(i,n+5) cur[i]=0;

			while(true)

			{

				LL add=dfs(s,t,1e12);

				if(add==0) break;

				ret+=add;

			}

		}

	}

}

int n,m,a[110],b[110],x[10010],y[10010],ans=0,X[110],Y[110][110],len=0,ss,tt;

bool isx[110],isy[110];

vector <pii> need;

int main()

{

  cin>>n;

  rep(i,n) scanf("%d%d",&a[i],&b[i]);

  cin>>m;

  rep(i,m)

  {

    scanf("%d%d",&x[i],&y[i]);--x[i];--y[i];

    int least=min(b[x[i]],b[y[i]]);

    if(a[x[i]]<least) ans+=least-a[x[i]],a[x[i]]=least;

    if(a[y[i]]<least) ans+=least-a[y[i]],a[y[i]]=least;

  }

  rep(i,m)

  {

    if(max(a[x[i]],a[y[i]])>=max(b[x[i]],b[y[i]])&&min(a[x[i]],a[y[i]])>=min(b[x[i]],b[y[i]])) continue;

    if(b[y[i]]>a[y[i]]) swap(x[i],y[i]);

    need.pb(mpr(x[i],y[i]));

    isx[x[i]]=true;isy[y[i]]=true;

  }

  ss=++len;tt=++len;

  rep(i,n)

  {

    if(isx[i])

    {

      X[i]=++len;

      maxFlow::add_edge(ss,X[i],b[i]-a[i]);

    }

    else if(isy[i])

    {

      repn(j,100) Y[i][j]=++len;

      repn(j,100)

      {

        if(j+1<=100) maxFlow::add_edge(Y[i][j+1],Y[i][j],1e12);

        maxFlow::add_edge(Y[i][j],tt,(j<=a[i] ? 0:1));

      }

    }

  }

  rep(i,need.size()) maxFlow::add_edge(X[need[i].fi],Y[need[i].se][b[need[i].fi]],1e12);

  maxFlow::n=len;

  ans+=maxFlow::max_flow(ss,tt);

  cout<<ans<<endl;

	return 0;

}

巴特西

[题解] Atcoder ARC 142 E Pairing Wizards 最小割

最新文章

热门文章