感谢!@[Freopen](/space/show?uid=30037)
by Zekrom @ 2019-05-26 13:03:47
感谢!
by 辰星凌 @ 2020-07-11 19:25:37
感谢
by Yingluosanqian @ 2020-10-08 12:00:10
感谢!![se](https://cdn.luogu.com.cn/upload/pic/62244.png)
by GBLoi @ 2021-03-30 20:42:12
感谢![qq](https://xn--9zr.tk/qq)
by Uzumaki @ 2021-06-25 15:39:42
thanks
by shadow46 @ 2021-06-30 19:36:38
不过我其实还是不太理解
my code:(89pt)
```c++
#include<bits/stdc++.h>
using namespace std;
const int M=1e7+5;
const int N=1e4+5;
const int inf=0x3f3f3f3f;
int a[N],b[N],c1[N],c2[N],vcnt,nxt[M],to[M],head[N],len[M],ecnt=1;
void add_edge(int u,int v,int w) {
nxt[++ecnt]=head[u];to[ecnt]=v;len[ecnt]=w;head[u]=ecnt;
nxt[++ecnt]=head[v];to[ecnt]=u;len[ecnt]=0;head[v]=ecnt;
}
int dis[N],n,m,s,t,gap[N];
void bfs()
{
memset(dis,-1,sizeof(dis));
memset(gap,0,sizeof(gap));
dis[t]=0,gap[0]=1;
queue<int>q;
q.push(t);
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=head[u];i;i=nxt[i]) {
int v=to[i];
if(dis[v]!=-1)continue;
q.push(v);
dis[v]=dis[u]+1,gap[dis[v]]++;
}
}
return;
}
long long maxflow;
long long dfs(int u,long long flow) {
if(u==t) return flow;
long long used=0;
for(int i=head[u];i;i=nxt[i]) {
int v=to[i];
if(len[i]&&dis[v]+1==dis[u])
{
int tmp=dfs(v,min(1ll*len[i],flow-used));
if(tmp) {
len[i]-=tmp;
len[i^1]+=tmp;
used+=tmp;
}
if(used==flow)return used;
}
}
--gap[dis[u]];
if(gap[dis[u]]==0)dis[s]=vcnt;
dis[u]++,gap[dis[u]]++;
return used;
}
long long ISAP()
{
vcnt=t+1;
for(bfs();dis[s]<vcnt;maxflow-=dfs(s,inf));
return maxflow;
}
int main() {
freopen("P1361_2.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),maxflow+=a[i];
for(int i=1;i<=n;i++)scanf("%d",&b[i]),maxflow+=b[i];
scanf("%d",&m);
s=0,t=n+m+1;
for(int i=1;i<=n;i++)add_edge(s,i,a[i]),add_edge(i,t,b[i]);
for(int i=1;i<=m;i++) {
int x,tot;
scanf("%d%d%d",&tot,&c1[i],&c2[i]);
for(int j=1;j<=tot;j++) {
scanf("%d",&x);
add_edge(i+n,x,inf),add_edge(x,i+n,inf);
}
add_edge(s,i+n,c1[i]),add_edge(i+n,t,c2[i]),maxflow+=c1[i],maxflow+=c2[i];
}
ISAP();
printf("%lld",maxflow);
return 0;
}
```
by shadow46 @ 2021-12-25 16:30:05
@[Blade_dance](/user/224863) 现在理解了,不用看了
by shadow46 @ 2021-12-27 20:43:16
这么错的人,可以试试这组数据:
```
4
0 0 0 0
0 0 0 0
3
2 100 0 1 2
2 0 0 2 3
2 0 100 3 4
```
by shadow46 @ 2021-12-27 21:08:09
@[Freopen](/user/30037) 感谢
by 油炸皮卡丘0vo @ 2022-08-12 10:14:33