题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1458
大体上同BZOJ_1711
具体来说，假设全部填上，于是要删尽量多的点
然后行放左边，列放右边，点拆开放中间
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int L = 100+9;
const int N = 50000+9;
const int M = 1000000;
const int INF = 1000000000;
int head[N],nxt[M],to[M],dis[N],cur[N],flow[M];
int n,m,X[L],Y[L],cx[L],cy[L],k,S,T,mat[L][L],vout;
queue<int> que;
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
#define id(x,y) (x+(y-1)*n)
inline void Add_Edge(int u, int v, int f) {
static int TT = 1;
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}
inline bool BFS(){
memset(dis,-1,sizeof(dis));
dis[S] = 0; que.push(S);
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
dis[to[i]] = dis[w] + 1, que.push(to[i]);
} return ~dis[T];
}
int DFS(int w, int f) {
if (w == T) return f;
else { int ret = 0;
for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) {
int tmp = DFS(to[i], min(f, flow[i]));
ret += tmp; f -= tmp; flow[i] -= tmp; flow[i^1] += tmp;
if (!f) break;
} return ret;
}
}
inline int Dinic(){
int ret = 0; while (BFS()) {
memcpy(cur,head,sizeof(head));
ret += DFS(S,INF);
} return ret;
}
int main(){
m = read(); n = read(); k = read(); S = 0, T = N-1; vout = n*m;
for (int i=1;i<=m;i++) Y[i] = read(), cy[i] = n;
for (int i=1;i<=n;i++) X[i] = read(), cx[i] = m;
for (int i=1,x,y;i<=k;i++) x = read(), y = read(), mat[x][y] = 1, cx[x]--, cy[y]--, vout--;
for (int i=1;i<=m;i++) if (cy[i] < Y[i]) puts("JIONG!"), exit(0);
for (int i=1;i<=n;i++) if (cx[i] < X[i]) puts("JIONG!"), exit(0);
for (int i=1;i<=n;i++) Add_Edge(S,i,cx[i]-X[i]);
for (int i=1;i<=m;i++) Add_Edge(n+i,T,cy[i]-Y[i]);
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if (!mat[i][j])
Add_Edge(m+n+id(i,j),m+n+m+n+id(i,j),1),
Add_Edge(i,m+n+id(i,j),1), Add_Edge(m+n+m+n+id(i,j),j+n,1);
printf("%d\n",vout-Dinic());
return 0;
}
My family always say that I am wasting my time here at web, however I know I am getting know-how everyday by reading thes good articles.
It’s impressive that you are getting thoughts from this article as well
as from our discussion made at this time.
Very descriptive post, I enjoyed that a lot.
Will there be a part 2?
Heya i am for the first time here. I came across this board
and I find It truly useful & it helped me out much. I hope to give something back and aid others like you aided me.
It’s amazing in support of me to have a site, which is valuable for my knowledge.
thanks admin
Amazing blog! Do you have any recommendations for aspiring writers?
I’m hoping to start my own site soon but I’m a
little lost on everything. Would you advise starting with a free platform like WordPress or go for a paid option? There are
so many choices out there that I’m completely
overwhelmed .. Any suggestions? Thank you!
Hey There. I found your blog the use of msn. That is a really neatly written article.
I will make sure to bookmark it and return to learn extra of
your useful information. Thank you for the post. I’ll definitely return.
Excellent way of describing, and fastidious article
to take data concerning my presentation subject, which i am going to deliver in institution of higher education.
Hi there, its fastidious post about media print, we all understand media is a impressive source of data.
Howdy very cool web site!! Guy .. Excellent .. Superb ..
I will bookmark your web site and take the feeds additionally?
I am glad to find numerous helpful information right here in the submit, we want develop more strategies on this regard,
thank you for sharing. . . . . .
Howdy, i read your blog occasionally and i own a similar one and i was just wondering if you get a lot
of spam comments? If so how do you reduce it, any plugin or anything you can advise?
I get so much lately it’s driving me crazy so any help
is very much appreciated.
Every weekend i used to pay a visit this web site, because i wish for enjoyment, since this this website
conations actually fastidious funny information too.
Hi there! This is kind of off topic but I need some advice from an established blog. Is it hard to set up your own blog? I’m not very techincal but I can figure things out pretty quick. I’m thinking about making my own but I’m not sure where to begin. Do you have any points or suggestions? Thank you
Excellent way of telling, and nice paragraph to get data regarding my presentation subject, which i am going
to present in college.
Saved as a favorite, I really like your blog!
WOW just what I was looking for. Came here by searching for match.com free
trial
It’s going to be finish of mine day, but before end I am reading this fantastic article to
improve my know-how.
Keep on writing, great job!
This paragraph provides clear idea in support of the new users of blogging, that really
how to do blogging.
Hello there, just became alert to your blog through Google, and found that it’s
truly informative. I’m going to watch out for brussels.
I’ll be grateful if you continue this in future.
A lot of people will be benefited from your writing. Cheers!
I really like your blog.. very nice colors & theme.
Did you create this website yourself or did you hire someone
to do it for you? Plz answer back as I’m looking to create my own blog and would like to know where u got this from.
many thanks
We absolutely love your blog and find nearly all of your post’s to be what precisely I’m looking
for. Does one offer guest writers to write content for you personally?
I wouldn’t mind producing a post or elaborating on a few
of the subjects you write related to here. Again, awesome
site!
This is a topic close to my heart cheers, where are your contact details though?