Submission #1403296
Source Code Expand
#include <iostream>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <algorithm>
#include <functional>
#include <cstring>
#include <limits.h>
#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define SZ(i) ((int)i.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define get0(x) (get<0>(x))
#define get1(x) (get<1>(x))
#define get2(x) (get<2>(x))
#define ALL(X) (X).begin(),(X).end()
#define LLMAX 9223372036854775807LL
#define LLMIN -9223372036854775808LL
#define IMAX 2147483647
#define IMIN -2147483648
typedef long long LL;
using namespace std;
#define MAX_V 1000
struct Edge{ int to,cap,rev; };
int used[MAX_V];
vector<Edge> G[MAX_V];
void addEdge(int from,int to,int cap){
G[from].push_back((Edge){to,cap,(int)G[to].size()});
G[to].push_back((Edge){from,0,(int)G[from].size()-1});
}
int DFS(int v,int t,int f){
if(v==t)
return f;
used[v]=true;
for(int i=0;i<(int)G[v].size();i++){
Edge &e=G[v][i];
if(!used[e.to] && 0<e.cap){
int d=DFS(e.to,t,min(f,e.cap));
if(0<d){
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int maxFlow(int s,int t){
int flow=0;
while(1){
for(int i=0;i<MAX_V;i++)
used[i]=false;
int f=DFS(s,t,INT_MAX);
if(f==0)
break;
flow+=f;
}
return flow;
}
int n,m,p,g;
int main(void){
cin>>n>>m>>p>>g;
REP(i,g){
int l;
cin>>l;
addEdge(m,l,IMAX);
}
REP(i,n){
int f,t,c;
cin>>f>>t>>c;
addEdge(f,t,c);
}
int r=maxFlow(m,0);
if(p<=r)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
H - お風呂は気持ちいい |
User |
a_kawashiro |
Language |
C++14 (GCC 5.4.1) |
Score |
140 |
Code Size |
2166 Byte |
Status |
AC |
Exec Time |
2 ms |
Memory |
256 KB |
Judge Result
Set Name |
f1t |
basic |
Score / Max Score |
40 / 40 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
f1t |
f1t/basic_case00, f1t/basic_case01, f1t/basic_case02, f1t/basic_case03, f1t/basic_case04, f1t/basic_case05, f1t/basic_case06, f1t/basic_case07, f1t/basic_case08, f1t/basic_case09, f1t/sample00, f1t/sample01, f1t/sample02 |
basic |
basic/basic_case00, basic/basic_case01, basic/basic_case02, basic/basic_case03, basic/basic_case04, basic/basic_case05, basic/basic_case06, basic/basic_case07, basic/basic_case08, basic/basic_case09, basic/corner00, basic/sample00, basic/sample01, basic/sample02 |
Case Name |
Status |
Exec Time |
Memory |
sample00 |
AC |
1 ms |
256 KB |
sample01 |
AC |
1 ms |
256 KB |
sample02 |
AC |
1 ms |
256 KB |
basic/basic_case00 |
AC |
1 ms |
256 KB |
basic/basic_case01 |
AC |
2 ms |
256 KB |
basic/basic_case02 |
AC |
1 ms |
256 KB |
basic/basic_case03 |
AC |
2 ms |
256 KB |
basic/basic_case04 |
AC |
2 ms |
256 KB |
basic/basic_case05 |
AC |
1 ms |
256 KB |
basic/basic_case06 |
AC |
1 ms |
256 KB |
basic/basic_case07 |
AC |
1 ms |
256 KB |
basic/basic_case08 |
AC |
2 ms |
256 KB |
basic/basic_case09 |
AC |
1 ms |
256 KB |
basic/corner00 |
AC |
1 ms |
256 KB |
basic/sample00 |
AC |
1 ms |
256 KB |
basic/sample01 |
AC |
1 ms |
256 KB |
basic/sample02 |
AC |
1 ms |
256 KB |
f1t/basic_case00 |
AC |
1 ms |
256 KB |
f1t/basic_case01 |
AC |
1 ms |
256 KB |
f1t/basic_case02 |
AC |
1 ms |
256 KB |
f1t/basic_case03 |
AC |
1 ms |
256 KB |
f1t/basic_case04 |
AC |
1 ms |
256 KB |
f1t/basic_case05 |
AC |
1 ms |
256 KB |
f1t/basic_case06 |
AC |
1 ms |
256 KB |
f1t/basic_case07 |
AC |
1 ms |
256 KB |
f1t/basic_case08 |
AC |
1 ms |
256 KB |
f1t/basic_case09 |
AC |
1 ms |
256 KB |
f1t/sample00 |
AC |
1 ms |
256 KB |
f1t/sample01 |
AC |
1 ms |
256 KB |
f1t/sample02 |
AC |
1 ms |
256 KB |