Subway Lines
题目链接： Subway Lines Gym - 101908L
题意
给你R个炼油厂，P个加油站，现在，每个炼油厂有着各自的储油量，每个加油站都有着需要的油量。现在给出一些匹配方路线，每条路线无油量运输限制，但跑一边路程会需要花费一定量的时间，问能否满足所有的加油站油量需要，如果可以满足，最少用多少时间？
数据范围：
R
,
P
<
1
0
3
R,P<10^3
R,P<103
思路
这题一看，如此分配问题，必定是用网络流没跑了，
但怎么建边呢，原先我想到是跑最小费用最大流，费用优先，但是细想一下，这个原理不同，最小费用最大流需要的是单位流量费用，而这里忽略了单位流量。
于是，我就在费用流的路上渐行渐远了。。。。。
其实，应该用普通的最大流，每次二分建边即可。
代码
#include <bits/stdc++.h>
using namespace std
;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define per(i,j,k) for(int i = (int)j;i >= (int)k;i --)
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef double db
;
typedef long long ll
;
const int MAXN
= (int)2e4+2007;
const int INF
= (int)0x3f3f3f3f;
struct edge
{
int to
,cap
,rev
;
edge(int to
= 0,int cap
= 0,int rev
= 0):to(to
),cap(cap
),rev(rev
){}
};
int SumOut
;
int N
,M
;
vector
<edge
> G
[MAXN
];
int level
[MAXN
];
int iter
[MAXN
];
void add_edge(int from
,int to
,int cap
) {
G
[from
].pb(edge(to
,cap
,G
[to
].size()));
G
[to
].pb(edge(from
,0,G
[from
].size()-1));
}
void bfs(int s
){
mmm(level
,-1);
queue
<int> qu
;
level
[s
] = 0;
qu
.push(s
);
while (!qu
.empty()) {
int v
= qu
.front(); qu
.pop();
rep(i
,0,G
[v
].size()-1) {
edge
&e
= G
[v
][i
];
if (e
.cap
> 0 && level
[e
.to
] < 0) {
level
[e
.to
] = level
[v
] + 1;
qu
.push(e
.to
);
}
}
}
}
int dfs(int v
,int t
,int f
) {
if (v
== t
) return f
;
for (int &i
= iter
[v
];i
< G
[v
].size();i
++) {
edge
&e
= G
[v
][i
];
if (e
.cap
> 0 && level
[v
] < level
[e
.to
]) {
int d
= dfs(e
.to
,t
,min(f
,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 (;;) {
bfs(s
);
if (level
[t
] < 0) return flow
;
mmm(iter
,0);
int f
;
while ((f
= dfs(s
,t
,INF
)) > 0)
flow
+= f
;
}
}
void init(){
rep(i
,1,N
) G
[i
].clear();
}
int P
,R
;
int in
[MAXN
];
int out
[MAXN
];
struct Node
{
int u
,v
,cost
;
Node(int u
= 0,int v
= 0,int cost
= 0):u(u
),v(v
),cost(cost
){}
};
Node tmp
[MAXN
];
int s
,t
;
bool OK(int m
) {
init();
rep(i
,1,M
) {
if (tmp
[i
].cost
<= m
) add_edge(tmp
[i
].u
,tmp
[i
].v
,INF
);
}
rep(i
,M
+1,R
+P
+M
) {
add_edge(tmp
[i
].u
,tmp
[i
].v
,tmp
[i
].cost
);
}
int res
= max_flow(s
,t
);
return res
== SumOut
;
}
int main()
{
scanf("%d %d %d",&P
,&R
,&M
);
rep(i
,1,P
) {
scanf("%d",&out
[i
]);
SumOut
+= out
[i
];
}
rep(i
,1,R
) scanf("%d",&in
[i
]);
N
= P
+R
;
s
= ++N
;
t
= ++N
;
rep(i
,1,M
) {
int x
,y
,w
;
scanf("%d %d %d",&x
,&y
,&w
);
tmp
[i
] = Node(y
,x
+R
,w
);
}
rep(i
,1,R
) {
tmp
[i
+M
] = Node(s
,i
,in
[i
]);
}
rep(i
,1,P
) {
tmp
[i
+M
+R
] = Node(i
+R
,t
,out
[i
]);
}
int l
= 0,r
= INF
;
while (l
<= r
) {
int m
= l
+r
>>1;
if (OK(m
)) r
= m
-1;
else l
= m
+1;
}
if (l
!= INF
+1) printf("%d\n",l
);
else printf("-1\n");
}
