UVA1104 Chips Challenge

一、題目

有一個 \(n\times n\) 的矩陣，每個元素可能是 .、C、/ 的其中一種，分別表示可以放置晶片、已經放置了晶片、不能放置晶片，你可以分別決定是否可以放置晶片的位置放置晶片。

最後需要滿足 \(\forall i\)，第 \(i\) 行的晶片個數等於第 \(i\) 列的晶片個數，每一行的晶片個數都不超過總晶片個數的 \(\frac{A}{B}\)，問在此情況下能額為放置的晶片個數最大值，如果怎麼樣都不合法輸出 impossible

\(n\leq 40\)

二、解法

如果直接做的話並不好入手，我們考慮調整法，也就是讓所有 . 的位置都放晶片再調整。

可以把晶片看成流量，我們可以套路地建出一個二分圖。想像第 \(i\) 行的點上具有 \(a_i\) 點流量，第 \(i\) 列的點上具有 \(b_i\) 點流量（分別表示初始狀態下它們的晶片個數），那麼個數相等的條件可以轉化成第 \(i\) 行和第 \(i\) 列同時減少 \(1\) 的流量。

但是最後點上就不能有殘餘流量，對於 . 的位置我們可以選擇不放，設它的位置是 \((i,j)\) 那麼它可以讓 \(i\) 行 \(j\) 列同時減少 \(1\) 的流量。在此基礎上我們還要最大化總晶片數，所以可以考慮增加費用這個意義，我們把同行同列的邊費用設置為 \(0\)，減少晶片的邊費用設置為 \(1\)，跑最小費用最大流即可。

還剩下最後一個限制：每一行的晶片個數都不超過總晶片個數A/B，我們可以枚舉每一行的晶片個數 \(k\)，把同行同列的流量設置為 \(k\)，最後可以得到總晶片數 \(sum\)，所以我們只需要判斷下面兩點：滿流；\(sum\cdot A\geq k\cdot B\)

三、總結

調整法考慮尋找一個特殊的初始狀態，再考慮如何描述增加\(/\)減少的過程。網路流加調整法的應用是常見的，類似的模型還有最小鏈覆蓋，它就是把初始設置有 \(n\) 個鏈來調整。

網路流是屬於圖論的，所以它的思維方法中也涉及到思考原問題中的元素怎麼對應到圖上的每個量上去，比如本題因為要最大化總晶片數我們才考慮增加費用這一維。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int M = 105;
const int inf = 0x3f3f3f3f;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,A,B,S,T,ans,tot,f[M],a[M],b[M];
int m,dis[M],pre[M],flow[M],lst[M];
struct edge{int v,f,c,next;}e[M*M];char s[M][M];
void add(int u,int v,int F,int c)
{
	e[++tot]=edge{v,F,c,f[u]},f[u]=tot;
	e[++tot]=edge{u,0,-c,f[v]},f[v]=tot;
}
int bfs()
{
	queue<int> q;
	for(int i=0;i<=T;i++)
		dis[i]=inf,flow[i]=pre[i]=lst[i]=0;
	dis[S]=0;flow[S]=inf;q.push(S);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=f[u];i;i=e[i].next)
		{
			int v=e[i].v,c=e[i].c;
			if(dis[v]>dis[u]+c && e[i].f>0)
			{
				dis[v]=dis[u]+c;
				flow[v]=min(flow[u],e[i].f);
				pre[v]=u;lst[v]=i;
				q.push(v);
			}
		}
	}
	return flow[T]>0;
}
void zxy(int k)
{
	int res=0,sum=0,all=0;
	S=0;T=2*n+1;tot=1;
	for(int i=0;i<=T;i++) f[i]=0;
	for(int i=1;i<=n;i++)
	{
		all+=a[i];
		add(S,i,a[i],0);
		add(i+n,T,b[i],0);
		add(i,i+n,k,0);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) if(s[i][j]=='.')
			add(i,j+n,1,1);
	while(bfs())
	{
		int t=T;
		sum+=flow[t];
		res+=flow[t]*dis[t];
		while(t)
		{
			e[lst[t]].f-=flow[T];
			e[lst[t]^1].f+=flow[T];
			t=pre[t];
		}
	}
	if(sum==all && k*B<=(sum-res)*A)
		ans=max(ans,sum-res);
}
void work()
{
	m=0;ans=-1;
	for(int i=1;i<=n;i++) a[i]=b[i]=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s[i]+1);
		for(int j=1;j<=n;j++)
		{
			m+=(s[i][j]=='C');
			a[i]+=(s[i][j]=='C' || s[i][j]=='.');
			b[j]+=(s[i][j]=='C' || s[i][j]=='.');
		}
	}
	for(int i=0;i<=n;i++) zxy(i);
	if(ans==-1) puts("impossible");
	else printf("%d\n",ans-m);
}
signed main()
{
	int Case=0;
	while(~scanf("%d %d %d",&n,&A,&B) && n+A+B)
	{
		printf("Case %d: ",++Case);
		work();
	}
}

Tags: 其它-----枚舉其它-----調整法圖論-----網路流