补充:原题每个点时限为2s
by revenger @ 2017-04-25 18:59:41
```cpp
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
#define ll long long
#define oo 1e18
#define N 300
#define M 100000
int n,m,s,t,i,j,x,y;
struct edge
{
int to,f;
ll w;
int next;
}l[M];int e;
int head[N];
void add(int x,int y,int f,const ll &w)
{
l[++e]=(edge){y,f,w,head[x]};head[x]=e;
l[++e]=(edge){x,0,-w,head[y]};head[y]=e;
}
ll g[N];
struct g_xiao
{
__inline__ __attribute((always_inline)) bool operator()(int y,int x)
{
return g[x]>g[y];
}
};
typedef __gnu_pbds::priority_queue<int,g_xiao> heap;
heap q;
heap::point_iterator dy[N];
ll base;
bool spfa()//反向跑最长路
{
for (i=1;i<t;++i) g[i]=-oo;
q.push(t);
do
{
x=q.top();dy[x]=0;
q.pop();
base=g[x];
for (i=head[x];i;i=l[i].next)
if (l[i^1].f&&g[y=l[i].to]<base-l[i].w)
{
g[y]=base-l[i].w;
if (dy[y]!=0) q.modify(dy[y],y);
else dy[y]=q.push(y);
}
}while (!q.empty());
return g[s]!=-oo;
}
#define I a[x]
bool ing[N];
bool Find;
int a[N];
void dfs(int x)//正向搜索
{
if (x==t)
{
Find=1;return ;
}
ing[x]=1;
int y;ll now=g[x];
for (;I;I=l[I].next)
if (l[I].f&&!ing[y=l[I].to]&&g[y]+l[I].w==now)
{
dfs(y);
if (Find)
{
--l[I].f;++l[I^1].f;
ing[x]=0;
return;
}
}
ing[x]=0;
}
int _e;
bool ans[N][N];
void get_ans()
{
for (i=2;i<=_e;i+=2)
if (!l[i].f)
ans[l[i+1].to][l[i].to]=1;
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j) printf("%d",ans[i][n+j]);
printf("\n");
}
}
ll dy_w[100];
int main()
{ //freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
s=n+m+1;t=s+1;
e=1;
for (i=1;i<100;++i) dy_w[i]=log2(i<<20)*1000000000;
for (i=1;i<=n;++i)
for (j=1;j<=m;++j)
{
scanf("%d",&x);
if (x) add(i,n+j,1,dy_w[x]);
}
_e=e;
for (i=1;i<=n;++i)
{
scanf("%d",&x);add(s,i,x,0);
}
for (i=1;i<=m;++i)
{
scanf("%d",&x);add(n+i,t,x,0);
}
while (spfa())
{
for (i=1;i<=t;++i) a[i]=head[i];
while (dfs(s),Find) Find=0;
}
get_ans();
}
```
by 库宇辰 @ 2017-04-25 19:42:05
这不是题解吗……
by revenger @ 2017-04-25 20:41:32
我说一下那个点打表是因为当时那个点有问题,一模一样的数据本地可以测过但是Luogu上过不掉,所以无奈才打的表
然后现在已经可以过去了
by sSay @ 2017-05-25 17:05:24