F - Direction Setting Gym - 103117F （网络最大流，把点和边都当成点来建图，重新建立边来保存点的数据）

题目： Gym - 103117F

思路：

给边上方向的时候可以理解为选其中一个点的入度加一，然后我们要尽可能的将每个值的度数值都不大于ai，所以如此建图：
原点连m个点（代表题目中的m个边），容量为1 ，代表一个边只能让一个点加一。m个点连各自的ui,vi（共n个点）。然后这n个点连终点，容量为ai；表示进可能的流满。maxflow表示将ai尽可能流满的值。答案为m-maxflow。判断的时候只需看代表边序号的点流向哪个点，如果都不流直接随便标。
转载： https://blog.csdn.net/accept_2333/article/details/117804242 膜拜大佬ORZ

#include 
using namespace std;
#define ri register int
#define  M 3005
template <class G> void read(G &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return ;
 } 
 
int n,m;
int T;
int head[10*M+10],nxt[10*M+10];long long val[10*M+10],to[10*M+10];
int cent=1;
void add(int a,int b,int c)
{
    to[++cent]=b;
    nxt[cent]=head[a];
    head[a]=cent;
    val[cent]=c;
}

int dep[10*M+10];
int aa[10*M+10];
int flag[10*M+10];
int bfs()
{
    for(ri i=0;i<=n+m+1;i++) dep[i]=0;
    dep[0]=1;
    queue <int> q;
    q.push(0);
    while(!q.empty())
    {
        int a=q.front();q.pop();
        for(ri p=head[a];p;p=nxt[p])
        {
            int b=to[p];
            if(dep[b]==0&&val[p]) ///////////////////////// val 是边的那个量不是点的 是val【P】 
            {
                dep[b]=dep[a]+1;
                q.push(b);
            }
        }
    }
    return dep[m+n+1];
    
}

long long dfs(int a,long long  in)
{
    
    if(a==m+n+1) return in;
    long long out=0;
    for(ri p=head[a];p&&in;p=nxt[p])
    {
        int b=to[p];
        if(dep[b]==dep[a]+1&&val[p])
        {
            long long res=dfs(b,min(in,val[p]));
            val[p]-=res;
            val[p^1]+=res;
            in-=res;
            out+=res;
            if(res) aa[a]=b;
        }
    }
    
    if(out==0) dep[a]=0;
    return out;
}
int main(){
    
    read(T);
    while(T--)
    {
        read(n);read(m);
        for(ri i=1;i<=n;i++)
        {
            int a;
            read(a);
            add(i,m+n+1,a);
            add(n+m+1,i,0);
        }
        for(ri i=1;i<=m;i++)
        {
            
            int a,b;
            read(a);read(b);flag[n+i]=b;
            add(0,n+i,1);
            add(n+i,0,0);
            add(n+i,a,1);
            add(a,n+i,0);
            add(n+i,b,1);
            add(b,n+i,0);
        }
        long long ans=0;
        while(bfs())
        {
            ans+=dfs(0,1e18);
        }
        
        printf("%lld\n",m-ans);
        
        for(ri i=n+1;i<=m+n;i++)
        {
            if(flag[i]==aa[i]) printf("0");
            else printf("1");
        }
        printf("\n");
        for(ri i=0;i<=cent;i++)
        {
            val[i]=0;to[i]=0;nxt[i]=0;
            head[i]=0;aa[i]=0;flag[i]=0;
        }
        cent=1;
    }
    
    
}