hdu 3061 전투 최대 권 폐쇄 도

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=3061
백 군 학 우 는 최근 에 무술 을 매우 열심히 배 웠 기 때문에 곧 천 책 군의 통수권 자로 승진 되 었 다.그 는 취임 첫날 매우 어 려 운 전투 에 직면 했다.
정찰병 의 보답 에 따 르 면 전방 에 모두 N 개의 성 이 있 는데 지세 의 원인 을 고려 하여 최종 적 으로 어떤 성 을 점령 하기 전에 반드시 다른 성 을 점령 해 야 한 다 는 결론 을 얻 었 다.
사실 지 도 를 토폴로지 그림 으로 볼 수 있 고 어떤 성 을 점령 하 는 것 은 그 모든 선구 적 인 결점 을 먼저 공격 해 야 한 다 는 것 을 의미한다.
소 백 은 또 하나의 조 사 를 통 해 모든 성 을 점령 하 는 것 이 그의 병력 에 얼마나 소모 되 는 지 알 게 되 었 다.(물론 한 성 을 점령 할 때마다 군 대 를 정비 하고 병력 을 확충 할 수 있 기 때문에 천 책 군의 병력 은 매우 방대 하 다.수익 을 고려 하지 않 으 면 그들 은 모든 성 을 공격 할 수 있다).
지금 은 소 백 통 수 를 도와 전투 계획 을 세우 고 어떤 도 시 를 공격 하 는 지 골 라 서 천 책 군 이 전투 후에 군용 이 가장 강해 지도 록 하 세 요.
 
제목 설명:제목 과 같다.
알고리즘 분석:최대 권 폐쇄 도의 물 문제.

  1 #include<iostream>

  2 #include<cstdio>

  3 #include<cstring>

  4 #include<cstdlib>

  5 #include<cmath>

  6 #include<algorithm>

  7 #include<queue>

  8 #define inf 0x7fffffff

  9 using namespace std;

 10 const int maxn=500+10;

 11 const int M = 250000+10;

 12 

 13 int n,m,from,to;

 14 struct node

 15 {

 16     int v,flow;

 17     int next;

 18 }edge[M*3];

 19 int head[maxn],edgenum;

 20 

 21 void add(int u,int v,int flow)

 22 {

 23     edge[edgenum].v=v ;edge[edgenum].flow=flow ;

 24     edge[edgenum].next=head[u] ;head[u]=edgenum++ ;

 25 

 26     edge[edgenum].v=u ;edge[edgenum].flow=0 ;

 27     edge[edgenum].next=head[v] ;head[v]=edgenum++ ;

 28 }

 29 

 30 int d[maxn];

 31 int bfs()

 32 {

 33     memset(d,0,sizeof(d));

 34     d[from]=1;

 35     queue<int> Q;

 36     Q.push(from);

 37     while (!Q.empty())

 38     {

 39         int u=Q.front() ;Q.pop() ;

 40         for (int i=head[u] ;i!=-1 ;i=edge[i].next)

 41         {

 42             int v=edge[i].v;

 43             if (!d[v] && edge[i].flow)

 44             {

 45                 d[v]=d[u]+1;

 46                 Q.push(v);

 47                 if (v==to) return 1;

 48             }

 49         }

 50     }

 51     return 0;

 52 }

 53 

 54 int dfs(int u,int flow)

 55 {

 56     if (u==to || flow==0) return flow;

 57     int cap=flow;

 58     for (int i=head[u] ;i!=-1 ;i=edge[i].next)

 59     {

 60         int v=edge[i].v;

 61         if (d[v]==d[u]+1 && edge[i].flow)

 62         {

 63             int x=dfs(v,min(edge[i].flow,cap));

 64             edge[i].flow -= x;

 65             edge[i^1].flow += x;

 66             cap -= x;

 67             if (cap==0) return flow;

 68         }

 69     }

 70     return flow-cap;

 71 }

 72 

 73 int dinic()

 74 {

 75     int sum=0;

 76     while (bfs()) sum += dfs(from,inf);

 77     return sum;

 78 }

 79 

 80 int main()

 81 {

 82     while (scanf("%d%d",&n,&m)!=EOF)

 83     {

 84         int a,b;

 85         memset(head,-1,sizeof(head));

 86         edgenum=0;

 87         from=n+1;

 88         to=from+1;

 89         int sum=0;

 90         for (int i=1 ;i<=n ;i++)

 91         {

 92             scanf("%d",&a);

 93             if (a>0) {sum += a ;add(from,i,a);}

 94             else add(i,to,-a);

 95         }

 96         for (int i=0 ;i<m ;i++)

 97         {

 98             scanf("%d%d",&a,&b);

 99             add(a,b,inf);

100         }

101         printf("%d
",sum-dinic());

102     }

103     return 0;

104 }