hdu 3061 最大权闭合子图

时间:2023-03-09 23:18:58
hdu 3061 最大权闭合子图

属于模板题吧。。。

 #include <cstdio>
#include <cstring>
#include <vector>
#define min(a,b) ((a)<(b)?(a):(b))
#define oo 0x3f3f3f3f
#define N 610
using namespace std; struct Edge {
int u, v, f;
Edge( int u, int v, int f ):u(u),v(v),f(f){}
};
struct Dinic {
int src, dst;
vector<Edge> edge;
vector<int> g[N];
int dep[N], cur[N], qu[N], bg, ed; void init( int n, int src, int dst ) {
this->src = src;
this->dst = dst;
for( int i=; i<=n; i++ )
g[i].clear();
edge.clear();
}
void adde( int u, int v, int f ) {
g[u].push_back( edge.size() );
edge.push_back( Edge(u,v,f) );
g[v].push_back( edge.size() );
edge.push_back( Edge(v,u,) );
}
bool bfs() {
memset( dep, , sizeof(dep) );
qu[bg=ed=] = src;
dep[src] = ;
while( bg<=ed ) {
int u=qu[bg++];
for( int t=; t<g[u].size(); t++ ) {
Edge &e = edge[g[u][t]];
if( e.f && !dep[e.v] ) {
dep[e.v] = dep[e.u]+;
qu[++ed] = e.v;
}
}
}
return dep[dst];
}
int dfs( int u, int a ) {
if( u==dst || a== ) return a;
int remain=a, past=, na;
for( int &t=cur[u]; t<g[u].size(); t++ ) {
Edge &e = edge[g[u][t]];
Edge &ve = edge[g[u][t]^];
if( e.f && dep[e.v]==dep[e.u]+ && (na=dfs(e.v,min(remain,e.f))) ) {
remain -= na;
past += na;
e.f -= na;
ve.f += na;
if( !remain ) break;
}
}
return past;
}
int maxflow() {
int flow = ;
while( bfs() ) {
memset( cur, , sizeof(cur) );
flow += dfs(src,oo);
}
return flow;
}
}D; int n, m;
int src, dst;
int wght[N], sum; int main() {
while( scanf("%d%d",&n,&m)== ) {
src = n+, dst = n+;
D.init( n+, src, dst );
sum = ;
for( int i=; i<=n; i++ ) {
scanf( "%d", wght+i );
if( wght[i]> )
D.adde( src, i, wght[i] ), sum += wght[i];
if( wght[i]< )
D.adde( i, dst, -wght[i] );
}
for( int i=,u,v; i<=m; i++ ) {
scanf( "%d%d", &u, &v );
D.adde( u, v, oo );
}
printf( "%d\n", sum - D.maxflow() );
}
}