【警钟撅烂】不知道第几个

网络流

建立虚拟源点汇点编号分别为0，n+1

然后初始化的时候从1到n....

调题调了两个小时

啊哈哈，被自己，蠢笑啦~

#include<bits/stdc++.h>
using namespace std;

const int N = 605;
const int M = 2505;

const int INF = (int)0x3f3f3f3f;

int edgeid=1;
int head[N];
struct edge
{
    int v;
    int w;
    int nxt;
}e[N*N*2];
inline void addedge(int u,int v,int w) 
{
    edgeid++;
    e[edgeid].v=v;
    e[edgeid].w=w;
    e[edgeid].nxt=head[u];
    head[u]=edgeid;
}

queue<int> q[M];

int n,m;
int st,ed;

int c[M];

int dep[N];
int cur[N];

int ans;

queue<int> qq;
bool Bfs()
{
    memset(dep,-1,sizeof(dep));
    for(int i=0;i<=n+1;i++) cur[i]=head[i]; //事故地段
    while(!qq.empty()) qq.pop();
    qq.push(st);
    dep[st]=0;
    while(!qq.empty())
    {
        int u=qq.front();
        qq.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(e[i].w && dep[v]==-1)
            {
                dep[v]=dep[u]+1;
                // cout<<v<<" "<<dep[v]<<endl;
                if(v==ed) return 1;
                qq.push(v);
            }
        }
    }
    return 0;
}

int Dfs(int u,int rst)
{
    if(!rst || (u==ed)) return rst;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        cur[u]=i;
        int f;
        if(dep[v]==dep[u]+1 && (f=Dfs(v,min(rst,e[i].w))))
        {
            e[i].w-=f;
            e[i^1].w+=f;
            sum+=f;
            rst-=f;
            if(rst==0) break;//余量优化 常数
        }
    }
    if(sum==0) dep[u]=0;//废点优化 常数
    return sum;
}


void Dinic()
{
    while(Bfs())
    {
        ans+=Dfs(st,INF);
    }
}

int main()
{
    // freopen("working.in","r",stdin);
    cin>>m>>n;
    st=0,ed=n+1;
    for(int i=1;i<=m;i++)  scanf("%d",&c[i]);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        for(int j=1;j<=x;j++)
        {
            int z;
            scanf("%d",&z);
            q[z].push(i);
        }
        scanf("%d",&x);
        addedge(i,ed,x);
        addedge(ed,i,0);
    }
    for(int i=1;i<=m;i++)
    {
        if(q[i].empty()) continue;
        addedge(st,q[i].front(),c[i]);
        addedge(q[i].front(),st,0);
        int lst=q[i].front();
        q[i].pop();
        while(!q[i].empty())
        {
            addedge(lst,q[i].front(),INF);
            addedge(q[i].front(),lst,0);
            lst=q[i].front();
            q[i].pop();
        }
    }
    Dinic();
    cout<<ans;
    return 0;
}