并且没有无解的情况
by lichenxi @ 2018-11-29 21:10:26
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i)
#define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i)
#define For(i,a,b) for(i=(a),i<=(b);++i)
#define Forward(i,a,b) for(i=(a),i>=(b);--i)
template<typename T>inline void read(T &x){
T f=1;x=0;char c;
for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=x*10+(c^48);
x*=f;
}
using namespace std;
void file(){
#ifndef ONLINE_JUDGE
freopen("water.in","r",stdin);
freopen("water.out","w",stdout);
#endif
}
const int MAXN=811;
static int n,m,k;
static int l[MAXN],c[MAXN];
static int ans;
static struct edge{
int v,w,f,nxt;
}p[MAXN*MAXN<<2];
static int head[MAXN],e=1,s,t,ss,tt;
static bool a[MAXN][MAXN];
inline void add(int u,int v,int f,int w,bool laz=1){
p[++e]=(edge){v,w,f,head[u]};head[u]=e;
if(laz)add(v,u,0,-w,0);
}
inline void init(){
read(n);read(m);read(k);
Rep(i,1,n)read(l[i]);
Rep(i,1,m)read(c[i]);
s=n+m+1;t=s+1;ss=t+1;tt=ss+1;
static int x,y,cnt,cnss=0,cntt=0;
Rep(i,1,k)read(x),read(y),a[x][y]=true;
Rep(i,1,n){
cnt=0;
Rep(j,1,m)if(!a[i][j]){
++cnt;
add(i,n+j,1,1);
}
if(cnt<l[i]){cout<<"JIONG!"<<endl;exit(0);}
add(s,i,cnt-l[i],0);if(l[i])add(ss,i,l[i],0);
cnss+=l[i];
}
Rep(i,1,m){
cnt=0;
Rep(j,1,n)if(!a[j][i])++cnt;
if(cnt<c[i]){cout<<"JIONG!"<<endl;exit(0);}
add(n+i,t,cnt-c[i],0);if(c[i])add(n+i,tt,c[i],0);
cntt+=c[i];
}
add(ss,t,cntt,0);add(s,tt,cnss,0);
add(t,s,0xFFFFFFF,0);
}
static int cur[MAXN],fee;
static int vis[MAXN],dis[MAXN];
static deque<int>G;
inline bool spfa(int s,int t){
memset(dis,0x3f,sizeof dis);
dis[s]=0;G.push_back(s);
static int u;vis[s]=true;
while(!G.empty()){
u=G.front();G.pop_front();
for(register int v=head[u];v;v=p[v].nxt)
if(p[v].f&&dis[p[v].v]>dis[u]+p[v].w){
dis[p[v].v]=dis[u]+p[v].w;
if(!vis[p[v].v]){
vis[p[v].v]=true;
if(G.empty()||dis[p[v].v]<dis[G.front()])
G.push_front(p[v].v);
else G.push_back(p[v].v);
}
}
vis[u]=false;
}
return dis[t]^dis[0];
}
int dfs(int u,int t,int flow=0xFFFFFFF){
if(!flow||u==t)return flow;
vis[u]=true;int sum=0;
for(register int &v=cur[u];v;v=p[v].nxt)
if(!vis[p[v].v]&&p[v].f&&dis[p[v].v]==dis[u]+p[v].w){
int f=dfs(p[v].v,t,min(flow,p[v].f));
p[v].f-=f;p[v^1].f+=f;
fee+=p[v].w*f;sum+=f;flow-=f;
}
vis[u]=false;
return sum;
}
inline void Dinic(int s,int t)
{while(spfa(s,t))memcpy(cur,head,sizeof head),dfs(s,t);}
inline void solve(){
Dinic(ss,tt);
cout<<fee<<endl;
}
int main(){
file();
init();
solve();
return 0;
}
你好这题好方便
by 零之执行人 @ 2018-11-29 21:19:07
@[wufeiyang001](/space/show?uid=131410)
希望更丰富的展现？使用Markdown
by Wen_kr @ 2018-11-29 21:20:59
我最开始写的建边的地方$add(i,j+n)$写成了$add(i,j)$，然后样例出无解，我就把判无解的删掉了，结果AC了
by lichenxi @ 2018-11-29 21:25:27
@[chen_zhe](/space/show?uid=8457)
by pufanyi @ 2019-03-16 19:16:15
@[Wen_kr](/user/25308) orz
by Juanzhang @ 2021-07-31 09:04:45