题解

82 条题解

  • 0
    @ 2015-12-09 20:30:14
  • 0
    @ 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 )
    {
    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
    @ 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

  • 0
    @ 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
    @ 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;
    };

    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
    @ 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

  • 0
    @ 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

  • 0
    @ 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=总收入-最小割=总收入-最大流

  • 0
    @ 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+当前弧

  • 0
    @ 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+分叉增广

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

    N,M总是搞反

    最大闭权和回路。。。

    Dinic解决

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

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

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

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

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

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

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

    懺悔...

    糾結...

    挖牆腳...

    對手指...

    天...

    樓下N位神牛~

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

    阿門...

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

    ...终于150题...

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

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

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

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

    当前弧很厉害...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Dinic+边表的时间真的很快

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

  • 0
    @ 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

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

    最大权闭合子图。。。

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

    链表,我们分手吧...

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

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

    节点居然忘加了...

    数组居然开小了...

信息

ID
1352
难度
6
分类
图结构 | 网络流 点击显示
标签
递交数
1722
已通过
425
通过率
25%
被复制
3
上传者