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
AC × 36
AC × 45
RE × 47
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