HDU 4289 Control(拆点+最大流)

#include
  
     
#include
   
     #include
    
      #include
     
       using namespace std; #define N 405 #define INF 0x7fffffff int n,m,k; int level[N]; struct node { int to,next; int cost; }edge[N*N]; int head[N]; int t_head[N]; int num[N]; int start,end; void init() { k=0; memset(head,-1,sizeof(head)); } int bfs(int s,int t)//对顶点进行标号、找出层次图 { memset(level,0,sizeof(level)); queue
      
       q; q.push(s); level[s]=1; while(!q.empty()) { int now=q.front(); q.pop(); int i; for( i=head[now];i!=-1;i=edge[i].next) { int y=edge[i].to; if(!level[y]&&edge[i].cost>0) { level[y]=level[now]+1; q.push(y); } } } return level[t]!=0;//汇点是否在层次图中 } int minn(int x,int y) { if(x
       
        0) { edge[t_head[s]].cost-=temp; edge[t_head[s]^1].cost+=temp; flow+=temp; cp-=temp; if(cp==0)break; } } } return flow; } int dinic() { int ans=0,flow=0; int i; while(bfs(start,end))//汇点不在层次图中、算法终止 { for( i=0;i<=end;i++) t_head[i]=head[i]; ans+=dfs(start,INF); } return ans; } void add(int x,int y,int val) { edge[k].to=y; edge[k].cost=val; edge[k].next=head[x]; head[x]=k++; edge[k].to=x; edge[k].cost=0; edge[k].next=head[y]; head[y]=k++; } int main() { //freopen(C:\Users\终将我要华丽的逆袭\Desktop\lx_Zz_in.txt,r,stdin); //freopen(C:\Users\终将我要华丽的逆袭\Desktop\lx_Zz_out.txt,w,stdout); while(scanf(%d%d,&n,&m)!=EOF) { init(); int x,y; start=0;end=200+n+1; scanf(%d%d,&x,&y); int i; add(start,x,INF); add(y+200,end,INF); for( i=1;i<=n;i++) { scanf(%d,&num[i]); } for( i=1;i<=n;i++) { add(i,i+200,num[i]); add(i+200,i,num[i]); } for( i=1;i<=m;i++) { int a,b; scanf(%d%d,&a,&b); add(a+200,b,INF); add(b+200,a,INF); } printf(%d ,dinic()); } return 0; }