tyvj P 1431[Tyvj Jan]アサイメントタスク(最大ストリーム)

P 1431[Tyvj Jan]アサイメントタスク
時間:1000 ms/空間:131072 KiB/Javaクラス名:Main
説明
     tyvjの発展に伴い、管理者の任務はますます重くなり、どのように合理的に任務を分配するかは、研究可能な命題となっている.Tyvjには現在、M個のタスクとN人の管理者が必要です.各管理者のオンライン時間は一定ではなく、一人一人がd[i]単位のオンライン時間を持ち、一人一人の管理者が1つの単位の時間で1つのタスクを完了することができ、1つのタスクは1人の管理者しか完成できない(より多くの管理者が参加すると混乱する可能性がある).管理者ごとに能力が異なるため、完了できるタスクセットが異なる場合があります.最終的には、未完了のすべてのタスクの数を最小限に抑えます.
入力フォーマット
入力ファイルの最初には、NとMの2つの正の整数があります.
   次のN行は、1行ごとに管理者の情報を表し、1番目の正の整数はd[i]であり、2番目の正の整数はtotであり、後にtotの数があり、i番目の管理者が完了できるタスクの集合を示す.
出力フォーマット
出力ファイルは1つの数しかなく、すべての未完了タスクの最小値です.
試験例1
入力
3 3
2 2 1 2
0 3 1 2 3
1 1 2
しゅつりょく
1
コメント
データ範囲の規則:
20%のデータ n<=10 M<=10 かつD[i]=1
60%のデータ n<=50 M<=300 そしてD[i]<=30
100%のデータ n<=3000 M<=10000 かつd[i]<=100
admin TYVJ第1回月場所第3コース
 
【考え方】
       最大ストリーム.裸の問題.
       Dinicアルゴリズムの時間的複雑度はO(nm)であった.
【コード】
 

 1 #include
 2 #include
 3 #include
 4 #include
 5 #define FOR(a,b,c) for(int a=(b);a 6 using namespace std;
 7 
 8 const int maxn = 15000+10;
 9 const int INF = 1e9;
10 
11 struct Edge{
12     int u,v,cap,flow;
13 };
14 struct Dinic {
15     int n,m,s,t;
16     bool vis[maxn];
17     int d[maxn],cur[maxn];
18     vector<int> G[maxn];
19     vector es;
20     
21     void init(int n) {
22         this->n=n;
23         es.clear();
24         for(int i=0;i) G[i].clear();
25     }
26     void AddEdge(int u,int v,int cap) {
27         es.push_back((Edge){u,v,cap,0});
28         es.push_back((Edge){v,u,0,0});
29         m=es.size();
30         G[u].push_back(m-2);
31         G[v].push_back(m-1);
32     }
33     
34     bool BFS() {
35         queue<int> q;
36         memset(vis,0,sizeof(vis));
37         q.push(s); vis[s]=1; d[s]=0;
38         while(!q.empty()) {
39             int u=q.front(); q.pop();
40             for(int i=0;i) {
41                 Edge& e=es[G[u][i]];
42                 int v=e.v;
43                 if(!vis[v] && e.cap>e.flow) {
44                     vis[v]=1;
45                     d[v]=d[u]+1;
46                     q.push(v);
47                 }
48             }
49         }
50         return vis[t];
51     }
52     int DFS(int u,int a) {
53         if(u==t || a==0) return a;
54         int flow=0,f;
55         for(int& i=cur[u];i){
56             Edge& e=es[G[u][i]];
57             int v=e.v;
58             if( d[v]==d[u]+1 && (f=DFS(v,min(a,e.cap-e.flow)))>0 ) {
59                 e.flow+=f;
60                 es[G[u][i]^1].flow-=f;
61                 flow+=f,a-=f;
62                 if(!a) break;
63             }
64         }
65         return flow;
66     }
67     int Maxflow(int s,int t) {
68         this->s=s , this->t=t;
69         int flow=0;
70         while(BFS()) {
71             memset(cur,0,sizeof(cur));
72             flow+=DFS(s,INF);
73         }
74         return flow;
75     }
76 } dc;
77 
78 int n,m;
79 
80 int main() {
81     scanf("%d%d",&n,&m);
82     dc.init(n+m+2);
83     int s=n+m,t=s+1;
84     int x,a,b;
85     FOR(i,0,n) {
86         scanf("%d",&x);
87         dc.AddEdge(s,i,x);
88         scanf("%d",&a);
89         while(a--) {
90             scanf("%d",&b); b--;
91             dc.AddEdge(i,n+b,1);
92         }
93     }
94     FOR(i,0,m) dc.AddEdge(n+i,t,1);
95     int flow=dc.Maxflow(s,t);
96     printf("%d
",m-flow);
97     return 0;
98 }