AC的故事大结局山寨版（下）（最大流）

福建工程学院第十二届ACM程序设计大赛真题

AC的故事大结局山寨版（下）

TimeLimit:2000MS MemoryLimit:128MB

64-bit integer IO format:%lld

已解决 | 点击收藏

Problem Description

小A算出幕后黑手的人员是如此之多，知道在我们华夏，手段通天者必然身居高位，仅仅靠他们的力量恐怕难以和他们对抗。

于是小A和小C找到了以前认识的检察官侯亮平，告诉侯亮平事情的始末后，他们立马通知赵东来安排了人手准备逮捕嫌疑人祁同伟（这么大的事居然没有事先向上级汇报就擅自行动）。

现在警厅里只有P<=100个警察，F<=100辆警车和C<=100把武器，每辆车和每把武器都有自己的特点，每个警察只会用其中的一些警车和武器。

每辆警车只坐一名警察（不知道为何要这么浪费资源，可能市局比较有钱），每位警察必须带上自己熟练的武器才能驾车出击。

为了打败幕后黑手祁同伟，小A合理安排后派出了最多的人手，相信你也一定知道派出了多少警察。最终成功逮捕了嫌疑人祁同伟。

从此小A和小C过上了幸福快乐的日子。可喜可贺，可喜可贺。

Input

先输入一个整数t（<=100）表示有多少组数据

每组输入3个整数P，F，C，(3个数都不超过100)分别表示警察人数，警车数量和武器数量。

接着第i行表示第i个警察的能力（共P行）。该行先输入两个整数x，y表示该警察会驾驶x辆汽车和y把武器，之后有x个整数表示警车的编号和y个整数表示武器的编号。

（警车编号：1~F，武器编号：1~C）

Output

每组输出一个整数，代表能带上武器驾车出击的警察最多有多少个
SampleInput
1

4 3 3

2 2 1 2 3 1

2 2 2 3 1 2

2 2 1 3 1 2

2 1 1 3 3
SampleOutput
3

思路：警察，武器，车都看作点，虚拟出源点汇点。保证源点到汇点必须经过一个警察，一个武器，一辆车。另外，警察要拆成两个点，为了避免警察被使用多次。所有关系作为流为1的边

正确的图：

错误的图：

如果有一个人可以使用多个武器多辆车，那么该警察可能被使用多次。如下图，警察1就会贡献流量2。

 #include <bits/stdc++.h>

 using namespace std;

 const int MAXN = ;

 const int MAXM = 1e4 + ;

 const int INF  = 0x7fffffff;

 typedef long long LL;

 int s, t, p, f, c;

 struct Edge {

     int to, w, next;

 } edge[MAXM * ];

 int first[MAXN], cur[MAXN], sign, dist[MAXN];

 inline void init() {

     for(int i = ; i < MAXN; i ++ ) {

         first[i] = -;

     }

     sign = ;

 }

 inline void add_edge(int u,int v,int w) {

     edge[sign].to = v, edge[sign].w = w;

     edge[sign].next = first[u], first[u] = sign++;

     edge[sign].to = u, edge[sign].w = ;

     edge[sign].next = first[v], first[v] = sign++;

 }

 bool bfs(int s,int t) {

     memset(dist, -, sizeof(dist));

     queue<int>que;

     que.push(s), dist[s] = ;

     while(!que.empty()) {

         int now = que.front();

         que.pop();

         if(now == t) {

             return ;

         }

         for(int i = first[now]; ~i; i = edge[i].next) {

             int to = edge[i].to, ww = edge[i].w;

             if(dist[to] == - && ww > ) {

                 dist[to] = dist[now] + ;

                 que.push(to);

             }

         }

     }

     return ;

 }

 int dfs(int s, int t, int max_flow) {

     if(s == t) {

         return max_flow;

     }

     for(int &i = cur[s]; ~i; i = edge[i].next) {

         int to = edge[i].to, ww = edge[i].w;

         if(dist[to] == dist[s] +  && ww > ) {

             int flow = dfs(to, t, min(max_flow, ww));

             if(flow > ) {

                 edge[i].w -= flow;

                 edge[i ^ ].w += flow;

                 return flow;

             }

         }

     }

     return ;

 }

 int dinic(int s, int t) {

     int ans = ;

     while(bfs(s, t)) {

         for(int i = ; i < MAXN; i ++ ) {

             cur[i] = first[i];

         }

         ans += dfs(s, t, INF);

     }

     return ans;

 }

 template<class T>

 inline bool nextInt(T &n)

 {

     T x = , tmp = ; char c = getchar();

     while((c < '' || c > '') && c != '-' && c != EOF) c = getchar();

     if(c == EOF) return false;

     if(c == '-') c = getchar(), tmp = -;

     while(c >= '' && c <= '') x *= , x += (c - ''),c = getchar();

     n = x*tmp;

     return true;

 }

 template<class T>

 inline void out(T n)

 {

     if(n < )

     {

         putchar('-');

         n = -n;

     }

     int len = ,data[];

     while(n)

     {

         data[len++] = n%;

         n /= ;

     }

     if(!len) data[len++] = ;

     while(len--) putchar(data[len]+);

 }

 int main() {

     int T;

     nextInt(T);

     while(T--) {

         nextInt(p), nextInt(f), nextInt(c);

         s = , t = ;

         init();

         for(int i = ; i <= f; i++ ) { ///s->car

             add_edge(s, i, );

         }

         for(int i = ; i <= p; i++ ) { ///line

             add_edge(i + , i + , );

         }

         for(int i = ; i <= c; i++ ) { ///gun->t

             add_edge(i + , t, );

         }

         for(int i = ; i <= p; i++ ) {

             int x, y, id;

             nextInt(x), nextInt(y);

             for(int j = ; j <= x; j++ ) { ///car

                 nextInt(id);

                 add_edge(id, i + , );

             }

             for(int j = ; j <= y; j++ ) { ///gun

                 nextInt(id);

                 add_edge(i + , id + , );

             }

         }

         out(dinic(s, t)), putchar('\n');

     }

     return ;

 }

巴特西

AC的故事大结局山寨版（下）（最大流）

AC的故事大结局山寨版（下）

最新文章

热门文章