Submission #58750
Source Code Expand
//========================================================================
/*
kitsune- library
【グラフ】最小費用流 (Minimum Cost Flow)
For documentation, see http://www.kitsunemimi.org/icpc/minimum_cost_flow.html
*/
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<utility>
#include<complex>
#include<float.h>
#include<limits.h>
#include<list>
using namespace std;
// (SCALE,WL,SINGLEFLOW) = 0, 0/1, 0 が普通最速, 0, 1, 1 が割と安全
#define SCALE 0
#define WL 1
#define SINGLEFLOW 1
#define OPT 1
/****************************************************************
short: short版
****************************************************************/
#if OPT == 0
template<class V, class COST>
class edge{
public:
int i, j;
COST cost2;
V flow, cap;
int dest( int f){ return i == f ?
j : i; }
V residue(int f){ return i == f ?
#if SCALE
INT_MAX : flow; }
#else
cap - flow : flow; }
#endif
COST cost(int f){ return i == f ?
cost2 : -cost2; }
void flow_add( int f, V r ){ i == f ?
flow += r : flow -= r; }
};
template<class V, class COST>
pair<bool, COST>
mincost(
int n,
const V *b0, V *b,
const vector< vector< int > > &adj,
edge<V,COST> *e, int m,
COST inf,
// バッファ領域; 各々 n 要素分確保すること
COST *d, COST *dr, COST *p,
int *prev, int *visit
)
{
int n1 = n - 1;
// initial equibilium flow and potential
for( int i = n1; i >= 0; -- i ){
b[i] = b0[i];
p[i] = 0;
}
for( int i = m - 1; i >= 0; -- i ){
if( e[i].cost2 < 0 ){
V r = e[i].cap;
e[i].flow = r;
b[e[i].i] -= r;
b[e[i].j] += r;
}
else
e[i].flow = 0;
}
V delta = 1;
#if SCALE
V bmax = 0;
for( int i = n1; i >= 0; -- i ){
if( b[i] < 0 )
bmax = max( bmax, - b[i] );
else
bmax = max( bmax, + b[i] );
}
while( delta <= (bmax>>1) ) delta <<= 1;
#endif
for( ; delta >= 1; delta >>= 1 ){
while( 1 ){
#if WL
priority_queue< pair<COST, int> > wl;
#endif
for( int i = n1; i >= 0; -- i ){
d[i] = inf;
if( b[i] >= delta ){
#if WL
wl.push( pair<COST, int>( -0, i) );
#endif
d[i] = 0;
}
}
#if WL
if( wl.empty() )
break;
#endif
memset( prev, 0xff, sizeof(int)*n );
memset( visit, 0x00, sizeof(int)*n );
int t = -1;
#if WL
while( !wl.empty() ){
int i = wl.top().second;
COST di = - wl.top().first;
wl.pop();
if( visit[i] )
continue;
#else
while( 1 ){
int i = min_element( d, d + n ) - d;
COST di = d[i];
if( di == inf )
break;
#endif
COST dbase = di + p[i];
dr[i] = di;
d[i] = inf;
visit[i] = 1;
#if SINGLEFLOW
if( t < 0 && b[i] <= -delta )
t = i;
#endif
for( vector<int>::const_iterator
J=adj[i].begin(), JE=adj[i].end();
J != JE; ++ J ){
edge<V,COST> &est = e[*J];
int j = est.dest( i );
if( visit[j] || est.residue(i)<=0 )
continue;
COST dj = dbase+est.cost(i)-p[j];
if( d[j] > dj ){
d[j] = dj;
prev[j] = *J;
#if WL
wl.push(pair<COST,int>(-dj, j));
#endif
}
}
} // dij end
for( int i = n1; i >= 0; -- i )
if( visit[i] ) p[i] += dr[i];
#if SINGLEFLOW
if( t >= 0 ){
#else
for( int t2 = n1; t2 >= 0; -- t2 ){
if( !visit[t2] || b[t2] > -delta )
continue;
t = t2;
#endif
int i, j;
//--------
// r を決定
#if SCALE && SINGLEFLOW
V r = delta;
#else
#if SCALE
V r = delta;
#else
V r = -b[t];
#endif
for( i = t; (j = prev[i]) >= 0; ){
edge<V,COST> &est = e[j];
i = est.dest( i );
r = min( r, est.residue( i ) );
}
r = min( r, b[i] );
#endif
if( r < delta )
continue;
//--------
// r だけ流す
for( i = t; (j = prev[i]) >= 0; ){
edge<V,COST> &est = e[j];
i = est.dest( i );
est.flow_add( i, r );
}
b[t] += r;
b[i] -= r;
}
if ( t == -1 ) // no feasible flow
break;
}}
// コスト総計を計算
COST cost_sum = 0;
bool is_b = true;
for( int i = m - 1; i >= 0; -- i )
cost_sum += e[i].cost2 * e[i].flow;
for( int i = n - 1; i >= 0; -- i ){
if( b[i] != 0 ){
is_b = 0;
break;
}
}
return pair<bool, COST>(is_b, cost_sum);
}
#endif
/****************************************************************
opt: 最適化版
****************************************************************/
#if OPT == 1
template<class V, class COST>
class edge{
public:
int i, j;
COST cost2;
V flow;
V cap;
};
template<class V, class COST>
pair<bool, COST>
mincost(
int n,
const V *b0, V *b,
const vector< vector< int > > &adj,
edge<V,COST> *e, int m,
COST inf,
// バッファ領域; 各々 n 要素分確保すること
COST *d, COST *dr, COST *p,
int *prev, int *visited
)
{
int n1 = n - 1;
// initial equibilium flow and potential
for( int i = n1; i >= 0; -- i ){
b[i] = b0[i];
p[i] = 0;
}
for( int i = m - 1; i >= 0; -- i ){
if( e[i].cost2 < 0 ){
V r = e[i].cap;
e[i].flow = r;
b[e[i].i] -= r;
b[e[i].j] += r;
}
else
e[i].flow = 0;
}
V delta = 1;
#if SCALE
V bmax = 0;
for( int i = n1; i >= 0; -- i ){
if( b[i] < 0 )
bmax = max( bmax, - b[i] );
else
bmax = max( bmax, + b[i] );
}
while( delta <= (bmax >> 1) ) delta <<= 1;
#endif
for( ; delta >= 1; delta >>= 1 ){ // until the flow becomes feasible
int flag_t = 0, flag_s = 0;
for( int i = n1; i >= 0; -- i ){
if( b[i] >= delta )
flag_s ++;
else if( b[i] <= -delta )
flag_t ++;
}
while( flag_t > 0 && flag_s > 0 ){
#if WL
priority_queue< pair<COST, int> > wl;
#endif
for( int i = n1; i >= 0; -- i ){
d[i] = inf;
if( b[i] >= delta ){
#if WL
wl.push( pair<COST, int>( -0, i) );
#endif
d[i] = 0;
}
// prev[i] = -1;
// visited[i] = 0;
}
#if WL
if( wl.empty() )
break;
#endif
memset( prev, 0xff, sizeof(int)*n );
memset( visited, 0x00, sizeof(int)*n );
int t = -1;
#if WL
while( !wl.empty() ){
int i = wl.top().second;
COST di = - wl.top().first;
wl.pop();
if( visited[i] )
continue;
COST dbase = di + p[i];
dr[i] = di;
#else
while( 1 ){
COST *jp = min_element( d, d + n );
if( *jp == inf )
break;
int i = jp - d;
COST dbase = *jp + p[i];
dr[i] = *jp;
*jp = inf;
#endif
visited[i] = 1;
#if SINGLEFLOW
if( t < 0 && b[i] <= -delta ) // sink
t = i;
#endif
for( vector<int>::const_iterator J = adj[i].begin(), JE = adj[i].end(); J != JE; ++ J ){
edge<V,COST> &est = e[*J];
if( est.j == i ){
if( est.flow > 0 && !visited[est.i] ){
COST dj = dbase - est.cost2 - p[est.i];
if( d[est.i] > dj ){
d[est.i] = dj;
prev[est.i] = *J;
#if WL
wl.push( pair<COST, int>( -dj, est.i ) );
#endif
}
}
}
else{
#if SCALE
if( !visited[est.j] ){
#else
if( est.flow < est.cap && !visited[est.j] ){
#endif
COST dj = dbase + est.cost2 - p[est.j];
if( d[est.j] > dj ){
d[est.j] = dj;
prev[est.j] = *J;
#if WL
wl.push( pair<COST, int>( -dj, est.j ) );
#endif
}
}
}
}
} // dij end
for( int i = n1; i >= 0; -- i )
if( visited[i] )
p[i] += dr[i];
#if SINGLEFLOW
{
if( t >= 0 ){
int t2 = t;
#else
for( int t2 = n1; t2 >= 0 && flag_t > 0 && flag_s > 0; -- t2 ){
if( visited[t2] && b[t2] <= -delta ){
t = t2;
#endif
int i, j;
//--------
// r を決定
#if SCALE && SINGLEFLOW
V r = delta;
#else
#if SCALE
V r = delta;
#else
V r = -b[t2];
#endif
for( i = t2; r > 0 && (j = prev[i]) >= 0; ){
edge<V,COST> &est = e[j];
if( est.i == i ){
r = min( r, est.flow );
i = est.j;
}
else{
#if !SCALE
r = min( r, est.cap - est.flow );
#endif
i = est.i;
}
}
r = min( r, b[i] );
#endif
//--------
// r だけ流す
if( r >= delta ){
for( i = t2; (j = prev[i]) >= 0; ){
edge<V,COST> &est = e[j];
if( est.i == i ){
est.flow -= r;
i = est.j;
}
else{
est.flow += r;
i = est.i;
}
}
b[t2] += r;
b[i] -= r;
if( b[i] < delta )
flag_s --;
if( b[t2] > -delta )
flag_t --;
}
}
}
if ( t == -1 ) // no feasible flow
break;
}
}
COST cost_sum = 0;
bool is_b = true;
for( int i = m - 1; i >= 0; -- i )
cost_sum += e[i].cost2 * e[i].flow;
for( int i = n - 1; i >= 0; -- i ){
if( b[i] != 0 ){
is_b = 0;
break;
}
}
return pair<bool, COST>(is_b, cost_sum);
}
#endif
//========================================================================
typedef edge<int, int> Edge;
int main()
{
int n, m, d;
cin >> n >> m >> d;
if (d != 1) { return 1; }
int gn = m + n + 2;
vector<int> gb0(gn, 0);
gb0[m + n] = n; gb0[m + n + 1] = -n;
vector<int> gb(gn, 0);
vector< vector<int> > ga(gn);
vector<Edge> ge;
int gm = 0;
for (int i = 0; i < m; i++) {
int ci, si, ki;
cin >> ci >> si >> ki;
{
Edge e;
e.i = m + n, e.j = i, e.cap = 1, e.cost2 = ci;
ge.push_back(e);
}
for (int j = 0; j < ki; j++) {
int aij;
cin >> aij; --aij;
Edge e;
e.i = i, e.j = m + aij, e.cap = 1, e.cost2 = 0;
ge.push_back(e);
}
}
for (int i = 0; i < n; i++) {
Edge e;
e.i = m + i, e.j = m + n + 1, e.cap = 1, e.cost2 = 0;
ge.push_back(e);
}
for (int i = 0; i < ge.size(); i++) {
ga[ge[i].i].push_back(i);
ga[ge[i].j].push_back(i);
}
vector<int> gd(gn), gdr(gn), gp(gn), gprev(gn), gvisit(gn);
pair<bool, int> r = mincost(
gn, &gb0[0], &gb[0], ga, &ge[0], ge.size(),
0xFFFFFFF, &gd[0], &gdr[0], &gp[0], &gprev[0], &gvisit[0]);
int b0; cin >> b0;
if (b0 < n) {
cout << -1 << endl;
} else {
cout << r.second << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
J - きたまさの逆襲 |
User |
yuizumi |
Language |
C++ (G++ 4.6.4) |
Score |
50 |
Code Size |
10540 Byte |
Status |
RE |
Exec Time |
55 ms |
Memory |
1048 KB |
Judge Result
Set Name |
Set 01 |
Set 02 |
Score / Max Score |
50 / 50 |
0 / 250 |
Status |
|
|
Set Name |
Test Cases |
Set 01 |
00_smallest.txt, 01_small_0.txt, 01_small_1.txt, 01_small_10.txt, 01_small_11.txt, 01_small_12.txt, 01_small_13.txt, 01_small_14.txt, 01_small_15.txt, 01_small_16.txt, 01_small_17.txt, 01_small_18.txt, 01_small_19.txt, 01_small_2.txt, 01_small_3.txt, 01_small_4.txt, 01_small_5.txt, 01_small_6.txt, 01_small_7.txt, 01_small_8.txt, 01_small_9.txt, 02_large_0.txt, 02_large_1.txt, 02_large_2.txt, 02_large_3.txt, 02_large_4.txt, 02_large_5.txt, 02_large_6.txt, 02_large_7.txt, 02_large_8.txt, 02_large_9.txt, 09_largest_0.txt, 09_largest_1.txt, 09_largest_2.txt, 09_largest_3.txt, 09_largest_4.txt |
Set 02 |
00_smallest.txt, 01_small_0.txt, 01_small_1.txt, 01_small_10.txt, 01_small_11.txt, 01_small_12.txt, 01_small_13.txt, 01_small_14.txt, 01_small_15.txt, 01_small_16.txt, 01_small_17.txt, 01_small_18.txt, 01_small_19.txt, 01_small_2.txt, 01_small_3.txt, 01_small_4.txt, 01_small_5.txt, 01_small_6.txt, 01_small_7.txt, 01_small_8.txt, 01_small_9.txt, 02_large_0.txt, 02_large_1.txt, 02_large_2.txt, 02_large_3.txt, 02_large_4.txt, 02_large_5.txt, 02_large_6.txt, 02_large_7.txt, 02_large_8.txt, 02_large_9.txt, 09_largest_0.txt, 09_largest_1.txt, 09_largest_2.txt, 09_largest_3.txt, 09_largest_4.txt, 10_smallest.txt, 11_small_0.txt, 11_small_1.txt, 11_small_10.txt, 11_small_11.txt, 11_small_12.txt, 11_small_13.txt, 11_small_14.txt, 11_small_15.txt, 11_small_16.txt, 11_small_17.txt, 11_small_18.txt, 11_small_19.txt, 11_small_2.txt, 11_small_20.txt, 11_small_21.txt, 11_small_22.txt, 11_small_23.txt, 11_small_24.txt, 11_small_25.txt, 11_small_26.txt, 11_small_27.txt, 11_small_28.txt, 11_small_29.txt, 11_small_3.txt, 11_small_4.txt, 11_small_5.txt, 11_small_6.txt, 11_small_7.txt, 11_small_8.txt, 11_small_9.txt, 12_large_0.txt, 12_large_1.txt, 12_large_10.txt, 12_large_11.txt, 12_large_12.txt, 12_large_13.txt, 12_large_14.txt, 12_large_15.txt, 12_large_16.txt, 12_large_17.txt, 12_large_18.txt, 12_large_19.txt, 12_large_2.txt, 12_large_3.txt, 12_large_4.txt, 12_large_5.txt, 12_large_6.txt, 12_large_7.txt, 12_large_8.txt, 12_large_9.txt, 19_largest_0.txt, 19_largest_1.txt, 19_largest_2.txt, 19_largest_3.txt, 19_largest_4.txt |
Case Name |
Status |
Exec Time |
Memory |
00_smallest.txt |
AC |
20 ms |
692 KB |
01_small_0.txt |
AC |
19 ms |
776 KB |
01_small_1.txt |
AC |
19 ms |
784 KB |
01_small_10.txt |
AC |
19 ms |
784 KB |
01_small_11.txt |
AC |
19 ms |
784 KB |
01_small_12.txt |
AC |
20 ms |
788 KB |
01_small_13.txt |
AC |
19 ms |
788 KB |
01_small_14.txt |
AC |
20 ms |
788 KB |
01_small_15.txt |
AC |
19 ms |
780 KB |
01_small_16.txt |
AC |
19 ms |
784 KB |
01_small_17.txt |
AC |
40 ms |
792 KB |
01_small_18.txt |
AC |
20 ms |
700 KB |
01_small_19.txt |
AC |
19 ms |
780 KB |
01_small_2.txt |
AC |
18 ms |
784 KB |
01_small_3.txt |
AC |
19 ms |
780 KB |
01_small_4.txt |
AC |
20 ms |
784 KB |
01_small_5.txt |
AC |
20 ms |
780 KB |
01_small_6.txt |
AC |
46 ms |
788 KB |
01_small_7.txt |
AC |
19 ms |
780 KB |
01_small_8.txt |
AC |
19 ms |
780 KB |
01_small_9.txt |
AC |
19 ms |
784 KB |
02_large_0.txt |
AC |
37 ms |
1036 KB |
02_large_1.txt |
AC |
25 ms |
784 KB |
02_large_2.txt |
AC |
47 ms |
836 KB |
02_large_3.txt |
AC |
29 ms |
1040 KB |
02_large_4.txt |
AC |
30 ms |
952 KB |
02_large_5.txt |
AC |
45 ms |
1040 KB |
02_large_6.txt |
AC |
43 ms |
980 KB |
02_large_7.txt |
AC |
27 ms |
916 KB |
02_large_8.txt |
AC |
25 ms |
908 KB |
02_large_9.txt |
AC |
24 ms |
800 KB |
09_largest_0.txt |
AC |
54 ms |
948 KB |
09_largest_1.txt |
AC |
55 ms |
940 KB |
09_largest_2.txt |
AC |
53 ms |
1036 KB |
09_largest_3.txt |
AC |
52 ms |
1048 KB |
09_largest_4.txt |
AC |
51 ms |
1036 KB |
10_smallest.txt |
AC |
19 ms |
792 KB |
11_small_0.txt |
AC |
20 ms |
656 KB |
11_small_1.txt |
RE |
48 ms |
780 KB |
11_small_10.txt |
RE |
19 ms |
784 KB |
11_small_11.txt |
RE |
19 ms |
688 KB |
11_small_12.txt |
AC |
19 ms |
780 KB |
11_small_13.txt |
RE |
45 ms |
788 KB |
11_small_14.txt |
AC |
30 ms |
788 KB |
11_small_15.txt |
RE |
19 ms |
684 KB |
11_small_16.txt |
AC |
20 ms |
784 KB |
11_small_17.txt |
AC |
22 ms |
792 KB |
11_small_18.txt |
AC |
21 ms |
784 KB |
11_small_19.txt |
RE |
20 ms |
776 KB |
11_small_2.txt |
AC |
39 ms |
784 KB |
11_small_20.txt |
RE |
20 ms |
776 KB |
11_small_21.txt |
RE |
41 ms |
700 KB |
11_small_22.txt |
RE |
42 ms |
784 KB |
11_small_23.txt |
RE |
19 ms |
776 KB |
11_small_24.txt |
RE |
19 ms |
668 KB |
11_small_25.txt |
RE |
19 ms |
780 KB |
11_small_26.txt |
RE |
19 ms |
820 KB |
11_small_27.txt |
RE |
20 ms |
704 KB |
11_small_28.txt |
RE |
19 ms |
776 KB |
11_small_29.txt |
RE |
20 ms |
700 KB |
11_small_3.txt |
RE |
20 ms |
664 KB |
11_small_4.txt |
RE |
19 ms |
684 KB |
11_small_5.txt |
RE |
20 ms |
784 KB |
11_small_6.txt |
AC |
20 ms |
784 KB |
11_small_7.txt |
RE |
41 ms |
792 KB |
11_small_8.txt |
RE |
20 ms |
780 KB |
11_small_9.txt |
RE |
19 ms |
788 KB |
12_large_0.txt |
RE |
21 ms |
792 KB |
12_large_1.txt |
RE |
20 ms |
792 KB |
12_large_10.txt |
RE |
22 ms |
792 KB |
12_large_11.txt |
RE |
19 ms |
784 KB |
12_large_12.txt |
RE |
19 ms |
784 KB |
12_large_13.txt |
RE |
20 ms |
688 KB |
12_large_14.txt |
RE |
19 ms |
784 KB |
12_large_15.txt |
RE |
20 ms |
780 KB |
12_large_16.txt |
RE |
18 ms |
784 KB |
12_large_17.txt |
RE |
19 ms |
784 KB |
12_large_18.txt |
RE |
19 ms |
704 KB |
12_large_19.txt |
RE |
42 ms |
692 KB |
12_large_2.txt |
RE |
19 ms |
788 KB |
12_large_3.txt |
RE |
19 ms |
784 KB |
12_large_4.txt |
RE |
19 ms |
788 KB |
12_large_5.txt |
RE |
19 ms |
792 KB |
12_large_6.txt |
RE |
46 ms |
788 KB |
12_large_7.txt |
RE |
19 ms |
784 KB |
12_large_8.txt |
RE |
19 ms |
780 KB |
12_large_9.txt |
RE |
18 ms |
784 KB |
19_largest_0.txt |
RE |
19 ms |
780 KB |
19_largest_1.txt |
RE |
19 ms |
780 KB |
19_largest_2.txt |
RE |
19 ms |
688 KB |
19_largest_3.txt |
RE |
19 ms |
780 KB |
19_largest_4.txt |
RE |
20 ms |
700 KB |
sample1.txt |
AC |
20 ms |
784 KB |
sample2.txt |
AC |
19 ms |
808 KB |
sample3.txt |
RE |
19 ms |
780 KB |