[TJOI2011]P1418 题解
Drind
·
·
题解
题目给定一个 01 矩阵每行和每列的 1 的个数,求字典序最小的满足条件的矩阵.
如果只需要给出一个构造那么这题非常简单,只需要建立一个二分图,左边有 $n
显然这样的构造不满足字典序最小,于是我们想,对于每个边,肯定是更靠前的边更重要,那是否可以给每个边一个费用跑费用流呢?事实上也是不行的,如果要让边之间互相不影响的话,费用最大的边必须达到 $2^{nm}$,显然是会爆 long long 的,这种方法不可行.
那么,既然每条经过增广的边都代表这个点是 $1$ 的话,我们是否可以把这条边删掉再跑一遍最大流,判断这条边是否必须呢?
如果用这种思路做的话,首先我们先贪心地从大到小枚举每个点,先跑一遍最大流,然后看看这个点对应的边是否被增广,如果没有被增广说明这个点不必要,输出 $0$;如果这个点对应的边被增广,那么就删掉这条边,再跑一遍最大流,如果这次最大流还能找到一条增广路替代这条边的话,就说明这个点不必要,输出 $0$;如果第二次最大流找不到增广路了,说明这个点必要，输出 $1$.
不用考虑如果前面的点取 $0$ 后是否会对后面的点产生影响,因为只要求字典序最小,前面的尽可能小,后面的再大也无所谓.
代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
struct node
{
int to,nxt;
int flow;
}edge[500001];//链式前向星
int cnt=1,s,t,n,m;
int head[1021];
int cur[1021];
int dep[1021];
int r[10001];
int c[10001];
int id[201][201];//id数组代表点对应的边，其中第一维的n+1代表连向汇点的边，第二位的m+1代表连向源点的边
void add(int u,int v,int w)
{
edge[++cnt]={v,head[u],w};
head[u]=cnt;
edge[++cnt]={u,head[v],0};
head[v]=cnt;
}//一次加正向和反向边
//以下为dinic板子
bool bfs()
{
memset(dep,0,sizeof(dep));
queue<int> q;
dep[s]=1;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];~i;i=edge[i].nxt)
{
int v=edge[i].to;
if(!dep[v]&&edge[i].flow>0)
{
dep[v]=dep[u]+1;
q.push(v);
if(v==t)
return true;
}
}
}
return false;
}
int dfs(int u,int f)
{
if(u==t)
return f;
int r=f;
for(int i=head[u];~i&&r;i=edge[i].nxt)
{
int v=edge[i].to;
if(dep[v]==dep[u]+1&&edge[i].flow>0)
{
int temp=dfs(v,min(r,edge[i].flow));
if(!temp)
dep[v]=0;
edge[i].flow-=temp;
edge[i^1].flow+=temp;
r-=temp;
}
}
return f-r;
}
int dinic()
{
int mxflo=0;
while(bfs())
{
mxflo+=dfs(s,1e9);
}
return mxflo;
}//以上为dinic板子
int check(int x,int y)//check函数代表第(x,y)个点是否必须
{
dinic();
if(!r[x]||!c[y]) return 0;//如果没有0可以放了，则输出1
r[x]--,c[y]--;//假设放置0，行列0的数量都减一
if(edge[id[x][y]].flow)//如果这个点未被增广，则不必要，输出0
{
edge[id[x][y]].flow=0;//删除这个点对应的边，以防今后再次使用
return 1;
}
else
{
edge[id[x][y]^1].flow=0;//删除这条边，再次跑最大流，看看这条边是否必要
edge[id[x][y]].flow=0;
edge[id[x][m+1]^1].flow--;
edge[id[x][m+1]].flow++;
edge[id[n+1][y]^1].flow--;
edge[id[n+1][y]].flow++;
if(dinic()==1)//如果找到新的增广路替代则这个点不必要
return 1;
r[x]++;
c[y]++;
edge[id[n+1][y]].flow--;
edge[id[n+1][y]^1].flow++;
edge[id[x][m+1]].flow--;
edge[id[x][m+1]^1].flow++;//这个点必要，恢复原状
return 0;
}
}
int main()
{
memset(head,-1,sizeof(head));
cin>>n>>m;
s=n+m+1;
t=s+1;
for(int i=1;i<=n;i++) cin>>r[i];
for(int i=1;i<=m;i++) cin>>c[i];
for(int i=1;i<=n;i++)
{
id[i][m+1]=cnt+1;
add(s,i,r[i]);
for(int j=1;j<=m;j++)
{
if(i==1)
{
id[n+1][j]=cnt+1;
add(j+n,t,c[j]);
}
id[i][j]=cnt+1;
add(i,j+n,1);
}
}//建图，初始化id数组
for(int i=1;i<=n;i++) r[i]=m-r[i];//注意这里r和c数组已经被替换成0的数量
for(int i=1;i<=m;i++) c[i]=n-c[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<1-check(i,j);//对于每个点判断
cout<<endl;
}
}
```