82 条题解
-
0
acmicpc LV 9 @ 2015-12-09 20:30:14
最大权闭合图，Dinic
http://www.cnblogs.com/jimzeng/p/bzoj1497.html -
0
测试数据 #0: Accepted, time = 0 ms, mem = 24836 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 24832 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 24872 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 24868 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 24868 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 24872 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 24872 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 24872 KiB, score = 10
测试数据 #8: Accepted, time = 904 ms, mem = 28088 KiB, score = 10
测试数据 #9: Accepted, time = 920 ms, mem = 28092 KiB, score = 10
Accepted, time = 1884 ms, mem = 28092 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
#include <string.h>
#define s 0
#define t ( n + m + 1 )
#define inf 1000000000using namespace std;
struct edge
{
int x , y , cap;
edge( int x , int y , int cap ) : x( x ) , y( y ) , cap( cap ) {}
edge() {}
}e[2000000];vector < int > linker[55000 + 10];
int pos , n , m , a , b , c , temp , ans;inline void addedge( int x , int y , int cap )
{
linker[x].push_back( pos );
e[ pos++ ] = edge( x , y , cap );
linker[y].push_back( pos );
e[ pos++ ] = edge( y , x , 0 );
}int dist[55000 + 10];
int cur[55000 + 10];inline bool bfs()
{
queue < int > q;
q.push( s );
memset( cur , 0 , sizeof( cur ) );
memset( dist , -1 , sizeof( dist ) );
int now;
dist[s] = 0;
while( !q.empty() )
{
now = q.front() , q.pop();
for( register int i = 0 ; i < linker[ now ].size() ; i++ )
if( dist[ e[ linker[ now ][i] ].y ] == -1 && e[ linker[ now ][i] ].cap > 0 ) q.push( e[ linker[ now ][i] ].y ) , dist[ e[ linker[ now ][i] ].y ] = dist[ now ] + 1;
}
return dist[ t ] > 0;
}int dinic( int now , int low )
{
if( now == t || !low ) return low;
int temp;
for( register int i = cur[ now ] ; i < linker[ now ].size() ; i++ )
{
cur[ now ] = i;
if( dist[ e[ linker[ now ][i] ].y ] == dist[ now ] + 1 && e[ linker[ now ][i] ].cap > 0 && ( temp = dinic( e[ linker[ now ][i] ].y , min( low , e[ linker[ now ][i] ].cap ) ) ) )
{
e[ linker[ now ][i] ].cap -= temp;
e[ linker[ now ][i] ^ 1 ].cap += temp;
return temp;
}
}
return 0;
}int main()
{
cin >> n >> m;
for( register int i = 1 ; i <= n ; i++ ) scanf( "%d" , &a ) , addedge( i , t , a );
for( register int i = 1 ; i <= m ; i++ )
{
scanf( "%d %d %d" , &a , &b , &c );
addedge( i + n , a , inf );
addedge( i + n , b , inf );
addedge( s , i + n , c );
ans += c;
}
while( bfs() ) while( temp = dinic( s , inf ) ) ans -= temp;
cout << ans << endl;
return 0;
} -
0
dinic只用当前弧优化,以及BFS找到汇点就跳出,这样就非常快了....
测试数据 #0: Accepted, time = 0 ms, mem = 29760 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 29768 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 29764 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 29764 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 29760 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 29768 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 29760 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 29764 KiB, score = 10
测试数据 #8: Accepted, time = 78 ms, mem = 29760 KiB, score = 10
测试数据 #9: Accepted, time = 62 ms, mem = 29760 KiB, score = 10
Accepted, time = 170 ms, mem = 29768 KiB, score = 100
-
0
lx865712528 LV 6 @ 2014-08-23 20:08:24
dinic水过
测试数据 #0: Accepted, time = 0 ms, mem = 9380 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 9380 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 9384 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 9380 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 9388 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 9380 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 9388 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 9384 KiB, score = 10
测试数据 #8: Accepted, time = 140 ms, mem = 9388 KiB, score = 10
测试数据 #9: Accepted, time = 156 ms, mem = 9384 KiB, score = 10
Accepted, time = 311 ms, mem = 9388 KiB, score = 100###Block code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXV=5555,MAXE=555555,INF=0x3f3f3f3f;
struct Edge {
int u,v,next,f;
Edge() {};
Edge(int u,int v,int f,int next):u(u),v(v),f(f),next(next) {};
};
Edge edge[MAXE];
int head[MAXV],nEdge,dis[MAXV],cur[MAXV],que[MAXV],stk[MAXV],n,m;
int pv[MAXV],lim,de[MAXV];
void init() {
lim=0;
memset(de,0,sizeof(de));
memset(head,-1,sizeof(head));
nEdge=0;
}
void addedge(int a,int b,int f) {
edge[nEdge]=Edge(a,b,f,head[a]);
head[a]=nEdge++;
edge[nEdge]=Edge(b,a,0,head[b]);
head[b]=nEdge++;
}
bool bfs(int src,int dst) {
memset(dis,-1,sizeof(dis));
int front=0,tail=0;
dis[src]=0;
que[tail++]=src;
while(front<tail) {
int u=que[front++];
for(int i=head[u];i!=-1;i=edge[i].next) {
int v=edge[i].v,f=edge[i].f;
if(f&&dis[v]<0) {
dis[v]=dis[u]+1;
if(v==dst) return true;
que[tail++]=v;
}
}
}
return false;
}
int dinic(int st_no,int ed_no,int src,int dst) {
int i,x=src,p,totalFlow=0ll;
while(bfs(src,dst)) {
int top=0;
for(i=st_no;i<=ed_no;i++) cur[i]=head[i];
while(1) {
if(x==dst) {
int nowFlow=lim*n;
for(i=0;i<top;i++) {
if(edge[stk[i]].f<nowFlow) {
nowFlow=edge[stk[i]].f;
p=i;
}
}
totalFlow+=nowFlow;
for(i=0;i<top;i++) {
edge[stk[i]].f-=nowFlow;
edge[stk[i]^1].f+=nowFlow;
}
top=p;
x=edge[stk[top]].u;
}
for(i=cur[x];i!=-1;i=edge[i].next) if(edge[i].f&&dis[edge[i].v]==dis[x]+1) break;
cur[x]=i;
if(i!=-1) {
stk[top++]=i;
x=edge[i].v;
}
else {
if(!top) break;
dis[x]=-1;
x=edge[stk[--top]].u;
}
}
}
return totalFlow;
}
int main() {
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=n;i++) scanf("%d",&pv[i]);
while(m--) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
de[u]+=w;
de[v]+=w;
lim+=w;
addedge(u,v,w);
addedge(v,u,w);
}
int src=0,sink=n+1;
for(int i=1;i<=n;i++) {
addedge(src,i,lim);
addedge(i,sink,lim+2*pv[i]-de[i]);
}
printf("%d\n",(lim*n-dinic(src,sink,src,sink))/2);
return 0;
} -
0
sap水过
#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std;
#define MAXN 60000
struct node {
int t,v;
node *next;
node *other;
};node* head[MAXN];
int n,m;
int p[MAXN];
int a[MAXN],b[MAXN],c[MAXN];int INSERT(int s,int t,int v){
node *p=new(node);
(*p).t=t;
(*p).v=v;
(*p).next=head[s];
head[s]=p;
return 0;
}int sum=0;
int gap[MAXN],h[MAXN];
node *d[MAXN];
int sap(int v,int flow){
if (v==(n+m+2)) return flow;
int rec=0;
node *p=d[v];
while (p!=NULL){
if ((*p).v&&h[v]==(h[(*p).t]+1)){
int ret=sap((*p).t,min(flow-rec,(*p).v));
d[v]=p;
(p).v-=ret;
((*p).other).v+=ret;
if ((rec+=ret)==flow) return rec;
}
p=(*p).next;
}
if (!(--gap[h[v]])){
h[n+m+1]=n+m+2;
}
gap[++h[v]]++;
d[v]=head[v];
return rec;
}int main(){
scanf("%d%d",&n,&m);
for (int i=0;i++<n;){
scanf("%d",&p[i]);
head[i]=NULL;
INSERT(n+m+1,i,p[i]);
INSERT(i,n+m+1,0);
(*head[n+m+1]).other=head[i];
(*head[i]).other=head[n+m+1];
}
for (int i=0;i++<m;){
scanf("%d%d%d",&a[i],&b[i],&c[i]);
sum+=c[i];
INSERT(n+i,n+m+2,c[i]);
INSERT(n+m+2,n+i,0);
(*head[n+i]).other=head[n+m+2];
(*head[n+m+2]).other=head[n+i];
INSERT(a[i],n+i,0x7fffffff);
INSERT(n+i,a[i],0);
(*head[a[i]]).other=head[n+i];
(*head[n+i]).other=head[a[i]];
INSERT(b[i],n+i,0x7fffffff);
INSERT(n+i,b[i],0);
(*head[b[i]]).other=head[n+i];
(*head[n+i]).other=head[b[i]];
}
for (int i=0;i++<n+m+2;){
gap[i]=h[i]=0;
d[i]=head[i];
}
int flow=0;
gap[0]=n+m+2;
while (h[n+m+1]<n+m+2){
flow+=sap(n+m+1,0x7fffffff);
}
printf("%d\n",sum-flow);
return 0;
}
编译成功测试数据 #0: Accepted, time = 15 ms, mem = 2420 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2448 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 2668 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 2668 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 2672 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 2672 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 2676 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 2668 KiB, score = 10
测试数据 #8: Accepted, time = 468 ms, mem = 14568 KiB, score = 10
测试数据 #9: Accepted, time = 468 ms, mem = 14572 KiB, score = 10
Accepted, time = 1026 ms, mem = 14572 KiB, score = 100 -
0
Dinic就可以过了，没必要还写那么多麻烦的优化。
虽说最后两个点花的时间比较长……为什么我用Dinic就要这么久啊，测评机原因？？？
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 618ms
├ 测试数据 10：答案正确... 602ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：1220ms -
0
编译通过...├ 测试数据 01：答案正确...ms├ 测试数据 02：答案正确...ms├ 测试数据 03：答案正确...ms├ 测试数据 04：答案正确...ms├ 测试数据 05：答案正确...ms├ 测试数据 06：答案正确...ms├ 测试数据 07：答案正确...ms├ 测试数据 08：答案正确...ms├ 测试数据 09：答案正确...181ms├ 测试数据 10：答案正确...243msAccepted 有效得分：100 有效耗时：424ms
SAP+GAP+当前弧+非递归
最大权闭合图
Ans=总收入-最小割=总收入-最大流
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 259ms
├ 测试数据 10：答案正确... 369ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：628mssap+gap+当前弧
-
0
prince_hao LV 10 @ 2010-04-11 20:33:22
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 197ms
├ 测试数据 10：答案正确... 228ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：425mssap+gap+分叉增广
-
0
largelymfs LV 8 @ 2010-03-16 00:34:11
N,M总是搞反
最大闭权和回路。。。
Dinic解决 -
0
M36_slugger LV 10 @ 2010-03-06 16:49:48
├ 测试数据 09：答案正确... 1866ms
├ 测试数据 10：答案正确... 1678ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：3544ms…………楼下用的应该不是Vag 6K，不然就会像我这样了
Dinic+边表的时间真的很快本题网络流模型比较明显，不会的就去找NOI2006的题解吧
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 9ms
├ 测试数据 10：答案正确... 25ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：34ms边表+DINIC
acmicpc
LV 9
@ 2015-12-09 20:30:14
