1 #include 
     
      //最大权闭合子图模板题  2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 using namespace std; 8 #define min(a,b) ((a)<(b))?(a):(b) 9 #define max(a,b) ((a)>(b))?(a):(b) 10 #define MAXN 1111+10 11 #define MAXM 505000+10//M取N的平方倍 12 #define INF 0x3f3f3f3f 13 14 struct node 15 { 16 int n;//点编号 17 int w;//点权 18 }Node[MAXN]; 19 //链式前向星 20 struct enode 21 { 22 int t; 23 int w; //权值 24 int c; //流量 25 // int cost; 26 // int pre; //前向指针 27 int next; 28 }; 29 30 31 struct enode e[MAXM]; 32 int box[MAXN],ecnt; 33 //int etail[MAXN]; //尾部 34 void init() 35 { 36 ecnt=0; 37 memset(box,-1,sizeof(box)); 38 // memset(etail,-1,sizeof(etail)); //初始化尾部 39 } 40 void addedge(int f,int t,int c) //流量重载 41 { 42 e[ecnt].next=box[f]; 43 e[ecnt].t=t; 44 e[ecnt].c=c; 45 box[f]=ecnt++; 46 e[ecnt].next=box[t]; 47 e[ecnt].t=f; 48 e[ecnt].c=0; 49 box[t]=ecnt++; 50 } 51 int sap(int s,int t,int N)//最大流问题 52 { 53 int gap[MAXN],lvl[MAXN],cur[MAXN],pre[MAXN]; 54 int curflow,ans=0,u,tmp,neck,i; 55 memset(lvl,0,sizeof(lvl)); 56 memset(gap,0,sizeof(gap)); 57 memset(pre,-1,sizeof(pre)); 58 for(i=0;i
           
            e[cur[i]].c) 70 { 71 neck=i; 72 curflow=e[cur[i]].c; 73 } 74 } 75 for(i=s;i!=t;i=e[cur[i]].t) 76 { 77 tmp=cur[i]; 78 e[tmp].c-=curflow; 79 e[tmp^1].c+=curflow; 80 } 81 ans+=curflow; 82 u=neck; 83 } 84 for(i=cur[u];i!=-1;i=e[i].next) 85 if(e[i].c && lvl[u]==lvl[e[i].t]+1) 86 break; 87 if(i!=-1) 88 { 89 cur[u]=i; 90 pre[e[i].t]=u; 91 u=e[i].t; 92 } 93 else 94 { 95 if(--gap[lvl[u]]==0) 96 break; 97 cur[u]=box[u]; 98 for(tmp=N,i=box[u];i!=-1;i=e[i].next) 99 if(e[i].c)100 tmp=min(tmp,lvl[e[i].t]);101 lvl[u]=tmp+1;102 gap[lvl[u]]++;103 if(u!=s)104 u=pre[u];105 }106 }107 return ans;108 }109 int main()110 {111 int m,n,a,b,t;112 int i,j,k;113 int start,end,ans;114 while(scanf("%d%d",&n,&m)!=EOF) //;115 {116 start=ans=0;117 end=1+n;//终点编号118 init();119 for(i=1;i<=n;i++)120 {121 scanf("%d",&Node[i].w);122 if(Node[i].w>0)123 {124 ans+=Node[i].w;125 addedge(start,i,Node[i].w);//起点建边126 }127 else if(Node[i].w<0)128 {129 addedge(i,end,0-Node[i].w);//负点权点和终点相连130 }131 Node[i].n=i;132 }133 for(i=1;i<=m;i++)134 {135 scanf("%d%d",&a,&b);136 addedge(a,b,INF);137 }138 t=sap( start,end,end+1);139 printf("%d\n",ans-t);140 }141 return 0;142 }143 /*144 Sample Input145 146 5 5147 8148 -8149 -10150 12151 -10152 153 1 2154 2 5155 1 4156 3 4157 4 5158 159 Sample Output160 161 2162 */