網(wǎng)絡(luò)流水題。。點(diǎn)有容量，那就拆點(diǎn)，有多個(gè)源點(diǎn)和匯點(diǎn)，那就新引入源點(diǎn)和匯點(diǎn)，再求最大流。
這種太裸的題目基本上是拿來練手的。
#include <iostream>
using namespace std;
#define N 205
#define INF 1 << 29
int cap[N][N], dis[N], pre[N], cnt[N];
int ISAP(int src, int sink, int n)
{
int maxflow = 0, flow, u = src, v, d;
memset(dis, 0, sizeof(dis));
memset(cnt, 0, sizeof(cnt));
pre[src] = src;
cnt[src] = n;
while(dis[src] < n)
{
if(u == sink)
{
flow = INF;
for(int i = sink; i != src; i = pre[i])
if(cap[pre[i]][i] < flow)
flow = cap[pre[i]][i];
maxflow += flow;
u = src;
for(int i = sink; i != src; i = pre[i])
{
cap[pre[i]][i] -= flow;
cap[i][pre[i]] += flow;
}
}
for(d = n, v = 0; v < n; v++)
{
if(!cap[u][v]) continue;
d = d < dis[v] ? d : dis[v];
if(dis[v] + 1 == dis[u]) break;
}
if(v < n) pre[v] = u, u = v;
else
{
if(!(--cnt[dis[u]])) break;
++cnt[dis[u] = d + 1];
if(u != src) u = pre[u];
}
}
return maxflow;
}
int main()
{
int n, m, a, b, c, st, ed, cas = 1;
while(~scanf("%d", &n))
{
st = 0, ed = (n << 1) + 1;
memset(cap, 0, sizeof(cap));
for(int i = 1; i <= n; i++)
{
scanf("%d", &a);
cap[i][i + n] = a;
}
scanf("%d", &m);
for(int i = 0; i < m; i++)
{
scanf("%d %d %d", &a, &b, &c);
if(a == b) continue;
cap[a + n][b] += c;
}
scanf("%d %d", &a, &b);
for(int i = 0; i < a; i++)
{
scanf("%d", &c);
cap[st][c] = INF;
}
for(int i = 0; i < b; i++)
{
scanf("%d", &c);
cap[c + n][ed] = INF;
}
int ans = ISAP(st, ed, ed + 1);
printf("%d\n", ans);
}
return 0;
}