HDU 4289 网络源 求去掉最少点权值使得 起末点不连通

HDU 4289 网络流 求去掉最少点权值使得 起末点不连通

题意：

n个点 m条边

下面起点 和终点

n行表示点权值

m条无向边

 

问：

去掉一些点需要的花费为该点的点权值，问要最少多少花费可以使得起点 和 终点 不连通

 

网络流裸题，按题目直接可以建图；

 

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define ll int

#define N 80000
#define M 401
#define inf 536870912

inline int Max(int a,int b){return a<b?b:a;}
inline int Min(int a,int b){return a>b?b:a;}


struct Edge{
	int from, to, cap, nex;
}edge[N];

int head[M], edgenum;
void addedge(int u, int v, int cap){
	Edge E = { u, v, cap, head[u]};
	edge[ edgenum ] = E;
	head[u] = edgenum ++;

	Edge E1= { v, u, 0,   head[v]};
	edge[ edgenum ] = E1;
	head[v] = edgenum ++;
}
int sign[M], s, t;
bool BFS(int from, int to){
	memset(sign, -1, sizeof(sign));
	sign[from] = 0;

	queue<int>q;
	q.push(from);
	while( !q.empty() ){
		int u = q.front(); q.pop();
		for(int i = head[u]; i!=-1; i = edge[i].nex)
		{
			int v = edge[i].to;
			if(sign[v]==-1 && edge[i].cap)
			{
				sign[v] = sign[u] + 1, q.push(v);
				if(sign[to] != -1)return true;
			}
		}
	}
	return false;
}
int Stack[N], top, cur[N];
int dinic(){

	int ans = 0;
	while( BFS(s, t) )
	{
		memcpy(cur, head, sizeof(head));
		int u = s;		top = 0;
		while(1)
		{
			if(u == t)
			{
				int flow = inf, loc;//loc 表示 Stack 中 cap 最小的边
				for(int i = 0; i < top; i++)
					if(flow > edge[ Stack[i] ].cap)
					{
						flow = edge[Stack[i]].cap;
						loc = i;
					}

					for(int i = 0; i < top; i++)
					{
						edge[ Stack[i] ].cap -= flow;
						edge[Stack[i]^1].cap += flow;
					}
					ans += flow;
					top = loc;
					u = edge[Stack[top]].from;
			}
			for(int i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增广的边的下标
				if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break;
			if(cur[u] != -1)
			{
				Stack[top++] = cur[u];
				u = edge[ cur[u] ].to;
			}
			else
			{
				if( top == 0 )break;
				sign[u] = -1;
				u = edge[ Stack[--top] ].from;
			}
		}
	}
	return ans;
}
int n;


int main(){
	ll i,u,v,temp,m;
	while(~scanf("%d %d",&n,&m)){
		memset(head, -1, sizeof(head)); edgenum = 0;

		scanf("%d %d",&s,&t);
		s+=n;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&temp);
			addedge(i+n,i, temp);
		}

		while(m--)
		{
			scanf("%d %d",&u,&v);
				addedge(u, v+n, inf);
				addedge(v, u+n, inf);
		}
		printf("%d\n", dinic());
	}
	return 0;
}
/*
5 6
5 3
5
2
3
4
12
1 5
5 4
2 3
2 4
4 3
2 1

*/