程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3061 最大閉合權子圖

hdu 3061 最大閉合權子圖

編輯：C++入門知識

Battle

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 808 Accepted Submission(s): 392

Problem Description 由於小白同學近期習武十分刻苦，很快被晉升為天策軍的統帥。而他上任的第一天，就面對了一場極其困難的戰斗：
據偵查兵回報，前方共有N座城池，考慮到地勢原因，最終得到一個結論：攻占某些城池之前必須攻占另外一些城池。
事實上，可以把地圖看做是一張拓撲圖，而攻占某個城池，就意味著必須先攻占它的所有前驅結點。
小白還做了一份調查，得到了攻占每個城池會對他的兵力產生多少消耗（當然也可能會得到增長，因為每攻占一個城池，便可以整頓軍隊，擴充兵力，天策軍的兵力十分龐大，如果不考慮收益，他們可以攻取所有的城池）。
現在請你幫小白統帥做一份戰斗計劃，挑選攻打哪些城市，使得天策軍在戰斗過後軍容最為壯大。

Input 首先輸入一個N 代表有N個城池（1<= n <= 500）
接著輸入一個M，代表城池和城池之間的拓撲關系數。
接著輸入N個數字代表從1 到 N 編號城池的戰斗消耗（負數代表將要消耗天策軍兵力，正數表示天策軍可以獲得相應的戰斗收益）
最後M行每行2個數字 a，b，代表相應城池的編號。
表示攻占b之後才可以攻占a；

Output 天策軍最大能獲得多少戰斗收益
Sample Input

Sample Output

比較裸，直接1Y。

代碼：

/* ***********************************************
Author :rabbit
Created Time :2014/3/9 22:00:26
File Name :A.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 10000000
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=2010;
const int maxm=1002000;
struct Edge{
	int next,to,cap;
	Edge(){};
	Edge(int _next,int _to,int _cap){
		next=_next;to=_to;cap=_cap;
	}
}edge[maxm];
int head[maxn],tol,dep[maxn],gap[maxn];
void addedge(int u,int v,int flow){
    edge[tol]=Edge(head[u],v,flow);head[u]=tol++;
    edge[tol]=Edge(head[v],u,0);head[v]=tol++;
}
void bfs(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]++;int front=0,rear=0,Q[maxn];
    dep[end]=0;Q[rear++]=end;
    while(front!=rear){
        int u=Q[front++];
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].to;if(dep[v]==-1)
                Q[rear++]=v,dep[v]=dep[u]+1,gap[dep[v]]++;
        }
    }
}
int sap(int s,int t,int N){
	int res=0;bfs(s,t);
	int cur[maxn],S[maxn],top=0,u=s,i;
	memcpy(cur,head,sizeof(head));
	while(dep[s]edge[S[i]].cap)
				   temp=edge[S[i]].cap,id=i;
		    for( i=0;idep[edge[i].to])
					MIN=dep[edge[i].to],cur[u]=i;
			--gap[dep[u]];++gap[dep[u]=MIN+1];
			if(u!=s)u=edge[S[--top]^1].to;
		}
	}
	return res;
}
int in[maxn];
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
	 int n,m;
     while(~scanf("%d%d",&n,&m)){
		 int sum=0;
		 memset(head,-1,sizeof(head));tol=0;
		 for(int i=1;i<=n;i++){
			 int j;
			 scanf("%d",&j);
			 if(j>0){
				 sum+=j;
				 addedge(0,i,j);
			 }
			 else addedge(i,n+1,-j);
		 }
		 while(m--){
			 int i,j;
			 scanf("%d%d",&i,&j);
			 addedge(i,j,INF);
		 }
		 int cnt=sap(0,n+1,4*n+10);
		 cout<