Submission #00191

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstring>
#include<vector>
#include<limits>
#define rep(i,a) for(int i=0;i<(a);++i)
#define clr(a,v) memset((a),(v),sizeof(a))
const int MAX_N = 100000, INF = std::numeric_limits<int>::max()>>2;
struct edge
{
int to, cap, rev;
edge( int to, int cap, int rev )
: to(to), cap(cap), rev(rev)
{}
};
int n;
std::vector<edge> G[MAX_N];
void add_edge( int from, int to, int cap )
{
G[from].push_back( edge( to, cap, G[to].size() ) );
G[to].push_back( edge( from, 0, G[from].size()-1 ) );
return;
}
bool used[MAX_N];
int dfs( int v, int t, int f )
{
if( v == t )
return f;
used[v] = true;
rep( i, G[v].size() )
{
edge &e = G[v][i];
if( !used[e.to] && e.cap > 0 )
{
int d = dfs( e.to, t, std::min( t, e.cap ) );
if( d > 0 )
{
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
int max_flow( int s, int t )
{
int flow = 0;
for(;;)
{
clr( used, false );
int f = dfs( s, t, INF );
if( !f )
return flow;
flow += f;
}
}
int main()
{
scanf( "%d", &n );
rep( i, n )
{
int a, b;
scanf( "%d%d", &a, &b );
--a; --b;
add_edge( a, b, 1 );
}
int ma = 0;
rep( r, 1 )
{
bool fv[MAX_N];
clr( fv, false );
rep( i, n ) if( rand()%2 )
fv[i] = true;
int s = 0;
rep( i, n ) rep( j, G[i].size() ) if( fv[i]^fv[G[i][j].to] )
s += G[i][j].cap;
ma = std::max( ma, s );
}
printf( "%d %d\n", max_flow( 0, n-1 ), ma );
return 0;
}

ステータス

項目 データ
問題 0007 - 最小カットと最大カット
ユーザー名 Ysmr_Ry
投稿日時 2015-08-28 11:59:54
言語 C++11
状態 Compile Error
得点 0
ソースコード長 1594 Byte
最大実行時間 -
最大メモリ使用量

コンパイルメッセージ

./191.cpp: In function ‘int main()’:
./191.cpp:93:24: error: ‘rand’ was not declared in this scope
   rep( i, n ) if( rand()%2 )
                        ^

セット

セット 得点 Cases

テストケース

ファイル名 状態 実行時間 メモリ使用量 #