#include<bits/stdc++.h>
using namespace std;
const int N=210,M=1e5+10,K=110;
const int Inf=0x3f3f3f3f;
struct edge{
int to,next,w;
double cost;
}ed[M<<1];
int he[N],tot=-1;
double dis[N],p[K][K];
int cur[N],a[K],b[K];
bool is[K][K],vis[N];
int n,m,s,t;
void insert(int u,int v,int w,double c){
tot++;
ed[tot].to=v;
ed[tot].w=w;
ed[tot].cost=c;
ed[tot].next=he[u];
he[u]=tot;
}
bool spfa(){
for(int i=s;i<=t;i++) dis[i]=-Inf;
memset(vis,0,sizeof(vis));
queue<int>q;
dis[s]=0;vis[s]=1;
q.push(s);cur[s]=he[s];
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=he[u];i!=-1;i=ed[i].next){
int v=ed[i].to;
if(dis[v]<dis[u]+ed[i].cost&&ed[i].w){
dis[v]=dis[u]+ed[i].cost;
cur[v]=he[v];
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
return dis[t]!=-Inf;
}
int dfs(int u,int lim){
if(u==t) return lim;
vis[u]=1;
int flow=0;
for(int i=cur[u];i!=-1&&flow<lim;i=ed[i].next){
int v=ed[i].to;
cur[u]=i;
if(dis[v]==dis[u]+ed[i].cost&&ed[i].w&&!vis[v]){
int t=dfs(v,min(ed[i].w,lim-flow));
if(!t) continue;
ed[i].w-=t,ed[i^1].w+=t;
flow+=t;
}
}
vis[u]=0;
return flow;
}
int dinic(){
int res=0,flow;
while(spfa())
while(flow=dfs(s,Inf))
res+=flow;
return res;
}
int main()
{
memset(he,-1,sizeof(he));
scanf("%d %d",&n,&m);
s=0,t=n+m+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%lf",p[i][j]);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
insert(s,i,a[i],0),insert(i,s,0,0);
for(int i=1;i<=m;i++)
insert(i+n,t,b[i],0),insert(t,i+n,0,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
insert(i,j+n,1,p[i][j]*0.01);
insert(j+n,i,0,-p[i][j]*0.01);
}
dinic();
for(int u=1;u<=n;u++)
for(int i=he[u];i!=-1;i=ed[i].next)
if(!ed[i].w) is[u][ed[i].to-n]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
printf("%d",is[i][j]);
puts("");
}
return 0;
}
此代码漏洞百出,却拿到了最优解,求加强数据