【BZOJ 1711】[Usaco2007 Open] Dining吃饭

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1711

《网络流建模汇总》的例题
牛放中间,食物放左边,饮料放右边

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 400+9;
const int M = 1000000;
const int INF = 1000000000;

int S,T,f,d,n,head[N],nxt[M],to[M],flow[M],dis[N],cur[N];
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;
}

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(){
	n = read(); f = read(); d = read(); S = 0; T = N-1;
	for (int i=1;i<=f;i++) Add_Edge(S,i,1);
	for (int i=1;i<=d;i++) Add_Edge(i+f+n,T,1);
	for (int i=1;i<=n;i++) Add_Edge(f+i,f+n+d+i,1);
	for (int i=1,t1,t2;i<=n;i++) {
		t1 = read(); t2 = read(); 
		for (int j=1;j<=t1;j++) Add_Edge(read(),i+f,1);
		for (int j=1;j<=t2;j++) Add_Edge(i+f+n+d,read()+f+n,1);
	} printf("%d\n",Dinic());
	return 0;
}

20 thoughts to “【BZOJ 1711】[Usaco2007 Open] Dining吃饭”

  1. I believe this is one of the most significant information for me.
    And i am glad studying your article. But should commentary on some basic issues,
    The web site taste is great, the articles is in reality excellent :
    D. Just right task, cheers

  2. I know this if off topic but I’m looking into starting my own weblog and was curious
    what all is required to get set up? I’m assuming having a blog like
    yours would cost a pretty penny? I’m not very web savvy so I’m not 100% sure.
    Any recommendations or advice would be greatly appreciated.
    Many thanks

  3. An intriguing discussion is worth comment. I believe that you should write more
    about this subject matter, it may not be a taboo matter but generally people do
    not discuss these topics. To the next! Cheers!!

  4. Hey I know this is off topic but I was wondering if you knew of
    any widgets I could add to my blog that automatically tweet my
    newest twitter updates. I’ve been looking for a plug-in like this for quite some time and was hoping maybe you would have
    some experience with something like this. Please let me
    know if you run into anything. I truly enjoy reading your blog
    and I look forward to your new updates.

  5. I have been absent for some time, but now I remember why I used to love this website. Thanks , I¦ll try and check back more often. How frequently you update your site?

  6. I feel that is among the so much significant information for me.
    And i’m happy reading your article. But should remark on some
    basic things, The site taste is perfect, the
    articles is really excellent : D. Excellent activity, cheers

  7. Does your blog have a contact page? I’m having problems locating it but, I’d like to shoot you an email.
    I’ve got some ideas for your blog you might be interested
    in hearing. Either way, great blog and I look forward to seeing it develop over
    time.

  8. Thank you, I have recently been looking for info approximately this topic for a while and yours is the greatest I have discovered so far. But, what about the bottom line? Are you certain about the source?

Leave a Reply to sling tv Cancel reply

Your email address will not be published. Required fields are marked *