```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=100006;
const int inf=2e9+6;
int cnt=1,s,t,n,m,tot;
int head[maxn],dep[maxn];
struct Edge{
int to,nxt,w;
}e[maxn];
void add(int u,int v,int w)
{
e[++cnt].w=w;
e[cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
bool bfs()
{
memset(dep,0,sizeof(dep));
queue<int>q;
dep[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i>1;i=e[i].nxt){
int w=e[i].w,v=e[i].to;
if(w>0&&!dep[v]){
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[t]!=0;
}
int dfs(int u,int lim)
{
if(u==t) return lim;
int delta=lim, d;
for(int i=head[u];i>1 && delta;i=e[i].nxt){
int w=e[i].w,v=e[i].to;
if(w>0&&dep[v]==dep[u]+1){
d = dfs(v,min(w,delta));
if (d == 0)
dep[v] = 0;
//if(d>0){
e[i].w-=d;
e[i^1].w+=d;
delta -= d;
//}
}
}
return lim-delta;
}
int dini()
{
int res=0;
while(bfs()){
res+=dfs(s,0x7f7f7f7f);
}
return res;
}
int main()
{
scanf("%d%d",&m,&n);
s=0,t=n+m+1;
char ch[maxn];
for(int i=1;i<=m;++i){
cin.getline(ch,1000);
int len=strlen(ch);
if(len<=1){
--i;
continue;
}
int now=0,p=0,f=1;
while(p<=len){
if(isdigit(ch[p])){
now=now*10+ch[p]-'0';
}else{
if(f){
add(s,i,now);
add(i,s,0);
f=0;
tot+=now;
}else{
add(i,now+m,inf);
add(now+m,i,0);
}
now=0;
}
++p;
}
}
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
add(i+m,t,x);
add(t,i+m,0);
}
int ans=tot-dini();
for(int i=1;i<=m;i++){
if(dep[i]!=0) printf("%d ",i);
}
printf("\n");
for(int i=1;i<=n;i++){
if(dep[i+m]!=0) printf("%d ",i);
}
printf("\n%d",ans);
return 0;
}
```
应该只是Dinic的问题,修改的地方多打了空格为标记
by kimkim @ 2022-06-12 15:18:52
说错了,是dfs不是dinic
by kimkim @ 2022-06-12 15:26:15