# 82 条题解

• @ 2015-12-09 20:30:14
• @ 2015-12-04 23:38:08

测试数据 #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 1000000000

using 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 )
{
e[ pos++ ] = edge( x , y , cap );
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;
}

• @ 2015-05-05 21:16:27

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

• @ 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 pv[MAXV],lim,de[MAXV];
void init() {
lim=0;
memset(de,0,sizeof(de));
nEdge=0;
}
void addedge(int a,int b,int f) {
}
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++];
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;
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;
}
}
}
}
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;
}
int src=0,sink=n+1;
for(int i=1;i<=n;i++) {
}
printf("%d\n",(lim*n-dinic(src,sink,src,sink))/2);
return 0;
}

• @ 2013-08-22 12:17:12

sap水过
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAXN 60000

struct node {
int t,v;
node *next;
node *other;
};

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;
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]]++;
return rec;
}

int main(){
scanf("%d%d",&n,&m);
for (int i=0;i++<n;){
scanf("%d",&p[i]);
INSERT(n+m+1,i,p[i]);
INSERT(i,n+m+1,0);
}
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);
INSERT(a[i],n+i,0x7fffffff);
INSERT(n+i,a[i],0);
INSERT(b[i],n+i,0x7fffffff);
INSERT(n+i,b[i],0);
}
for (int i=0;i++<n+m+2;){
gap[i]=h[i]=0;
}
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

• @ 2010-07-17 11:03:48

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 196ms

├ 测试数据 10：答案正确... 181ms

• @ 2010-07-13 18:31:03

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

• @ 2010-07-09 08:56:30

编译通过...├ 测试数据 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=总收入-最小割=总收入-最大流

• @ 2010-04-11 20:59:26

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 259ms

├ 测试数据 10：答案正确... 369ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：628ms

sap+gap+当前弧

• @ 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 有效耗时：425ms

sap+gap+分叉增广

• @ 2010-03-16 00:34:11

N,M总是搞反

最大闭权和回路。。。

Dinic解决

• @ 2010-03-12 23:10:52

唉。。。为什么递归的就是比非递归的要慢那么多呢。。。。

• @ 2010-03-12 23:03:06

├ 测试数据 09：答案正确... 134ms

├ 测试数据 10：答案正确... 150ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：284ms

懺悔...

糾結...

挖牆腳...

對手指...

天...

樓下N位神牛~

XF積攢多年的RP,今日透支...

阿門...

• @ 2010-03-12 00:05:52

...终于150题...

├ 测试数据 09：答案正确... 212ms

├ 测试数据 10：答案正确... 228ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：440ms

当前弧很厉害...

• @ 2010-03-08 23:20:38

哎..和楼下的差距就是傻×和神牛的差距,,,悲剧之,,我也都加了为什么还是没达到效果,,,,,边好多,,注意开大点啊``\``童鞋们``害我悲剧一次,,300题哈`

Accepted 有效得分：100 有效耗时：378ms

• @ 2010-03-06 20:55:46

├ 测试数据 09：答案正确... 181ms

├ 测试数据 10：答案正确... 118ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：299ms

裸DINIC & Vag 6K 静态指针效果不错

• @ 2010-03-06 16:49:48

├ 测试数据 09：答案正确... 1866ms

├ 测试数据 10：答案正确... 1678ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3544ms

…………楼下用的应该不是Vag 6K，不然就会像我这样了

Dinic+边表的时间真的很快

本题网络流模型比较明显，不会的就去找NOI2006的题解吧

• @ 2010-03-05 21:31:53

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：34ms

边表+DINIC

• @ 2010-03-04 17:51:45

最大权闭合子图。。。

• @ 2009-10-31 16:13:53

链表，我们分手吧...

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：18ms

节点居然忘加了...

数组居然开小了...

ID
1352

6

1725

428

25%

4