50 条题解

  • 0
    @ 2016-04-11 22:29:27

    记录信息
    评测状态 Accepted
    题目 P1607 植物大战僵尸
    递交时间 2016-04-11 22:28:59
    代码语言 C++
    评测机 ShadowShore
    消耗时间 684 ms
    消耗内存 29764 KiB
    评测时间 2016-04-11 22:29:01
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 29760 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 29760 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 29760 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 = 29764 KiB, score = 10
    测试数据 #6: Accepted, time = 46 ms, mem = 29760 KiB, score = 10
    测试数据 #7: Accepted, time = 46 ms, mem = 29760 KiB, score = 10
    测试数据 #8: Accepted, time = 343 ms, mem = 29760 KiB, score = 10
    测试数据 #9: Accepted, time = 234 ms, mem = 29760 KiB, score = 10
    Accepted, time = 684 ms, mem = 29764 KiB, score = 100
    代码
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <queue>
    using namespace std;
    const int maxr=50,maxc=50;
    const int maxn=1050;
    const int maxm=200010;
    const int INF=23333333;
    int R,C,id[maxr][maxc],def[maxr*maxc],G[maxr*maxc][maxr*maxc],sum;
    int cnt=1,fir[maxn],nxt[maxm<<1],to[maxm<<1],cap[maxm<<1],v[maxr][maxc];
    void addedge(int a,int b,int c){
    nxt[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;cap[cnt]=c;
    }
    int dis[maxn],gap[maxn],path[maxn],fron[maxn];
    queue<int>q;
    void BFS(){
    memset(dis,0,sizeof(dis));
    dis[R*C+1]=1;q.push(R*C+1);
    while(!q.empty()){
    int x=q.front();q.pop();
    for(int i=fir[x];i;i=nxt[i])
    if(!dis[to[i]]&&!def[to[i]])
    dis[to[i]]=dis[x]+1,
    q.push(to[i]);
    }
    }
    int ISAP(){
    BFS();
    for(int i=0;i<=R*C+1;i++){
    gap[dis[i]]++;
    fron[i]=fir[i];
    }
    int p=0,f,ret=0;
    while(dis[0]<=R*C+2){
    if(p==R*C+1){
    f=INF;
    while(p){
    f=min(f,cap[path[p]]);
    p=to[path[p]^1];
    }
    p=R*C+1;ret+=f;
    while(p){
    cap[path[p]]-=f;
    cap[path[p]^1]+=f;
    p=to[path[p]^1];
    }
    }
    int &ii=fron[p];
    for(;ii;ii=nxt[ii])
    if(cap[ii]&&dis[to[ii]]==dis[p]-1&&!def[to[ii]])
    break;
    if(ii)
    path[p=to[ii]]=ii;
    else{
    if(--gap[dis[p]]==0)break;
    int Min=R*C+3;
    for(int i=fir[p];i;i=nxt[i])
    if(cap[i]&&!def[to[i]])
    Min=min(Min,dis[to[i]]);
    ++gap[dis[p]=Min+1];
    fron[p]=fir[p];
    if(p)p=to[path[p]^1];

    }

    }
    return ret;
    }
    void DFS(int x){
    for(int i=1;i<=R*C;i++)
    if(!def[i]&&G[x][i]){
    def[i]=true;
    DFS(i);
    }
    }
    int main(){
    //freopen("pvz.in","r",stdin);
    //freopen("pvz.out","w",stdout);
    scanf("%d%d",&R,&C);
    for(int i=1;i<=R;i++)
    for(int j=1;j<=C;j++)
    id[i][j]=(i-1)*C+j;
    for(int i=1;i<=R;i++)
    for(int j=1,x,a,b;j<=C;j++){
    scanf("%d%d",&v[i][j],&x);
    while(x--){
    scanf("%d%d",&a,&b);a++;b++;
    G[id[i][j]][id[a][b]]=true;
    addedge(id[a][b],id[i][j],INF);
    addedge(id[i][j],id[a][b],0);
    }
    if(j>1){
    G[id[i][j]][id[i][j-1]]=true;
    addedge(id[i][j-1],id[i][j],INF);
    addedge(id[i][j],id[i][j-1],0);
    }
    }

    for(int k=1;k<=R*C;k++)
    for(int i=1;i<=R*C;i++)
    for(int j=1;j<=R*C;j++)
    G[i][j]|=G[i][k]&&G[k][j];

    for(int i=1;i<=R*C;i++)
    if(G[i][i])
    def[i]=true;

    for(int i=1;i<=R*C;i++)
    if(def[i])
    DFS(i);

    for(int i=1;i<=R;i++)
    for(int j=1;j<=C;j++)
    if(!def[id[i][j]]){
    if(v[i][j]>0){
    sum+=v[i][j];
    addedge(0,id[i][j],v[i][j]);
    addedge(id[i][j],0,0);
    }
    else
    addedge(id[i][j],R*C+1,-v[i][j]),
    addedge(R*C+1,id[i][j],0);

    }

    printf("%d\n",sum-ISAP());

    return 0;
    }

  • 0
  • 0
    @ 2015-12-02 16:47:43

    测试数据 #0: Accepted, time = 0 ms, mem = 12032 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 12036 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 12028 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 12032 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 12028 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 12028 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 12028 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 12032 KiB, score = 10
    测试数据 #8: Accepted, time = 156 ms, mem = 14348 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 12044 KiB, score = 10
    Accepted, time = 171 ms, mem = 14348 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[1000000];

    vector < int > linker[600 + 10];
    int pos;

    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[600 + 10];
    int cur[600 + 10];
    int in[600 + 10];
    bool vis[600 + 10];
    int ans , temp;
    int n , m;
    int a[20 + 2][30 + 2] , x , y , r;

    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( vis[ e[ linker[ now ][i] ].y ] && 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;
    }

    inline int hernia( int x , int y )
    {
    return ( x - 1 ) * m + y;
    }

    inline void topo()
    {
    queue < int > q;
    for( register int i = s ; i <= t ; i++ )
    if( !in[i] ) q.push( i );
    int now;
    while( !q.empty() )
    {
    now = q.front() , q.pop();
    vis[ now ] = 1;
    for( register int i = 0 ; i < linker[ now ].size() ; i++ )
    if( !e[ linker[ now ][i] ].cap )
    {
    in[ e[ linker[ now ][i] ].y ]--;
    if( !in[ e[ linker[ now ][i] ].y ] ) q.push( e[ linker[ now ][i] ].y );
    }
    }
    vis[s] = vis[t] = 1;
    }

    int main()
    {
    scanf( "%d %d" , &n , &m );
    for( register int i = 1 ; i <= n ; i++ )
    for( register int j = 1 ; j <= m ; j++ )
    {
    scanf( "%d" , &a[i][j] );
    if( a[i][j] >= 0 ) addedge( s , hernia( i , j ) , a[i][j] ) , in[s]++;
    else addedge( hernia( i , j ) , t , -a[i][j] ) , in[ hernia( i , j ) ]++;
    scanf( "%d" , &r );
    for( register int k = 1 ; k <= r ; k++ )
    scanf( "%d %d" , &x , &y ) , addedge( hernia( x + 1 , y + 1 ) , hernia( i , j ) , inf ) , in[ hernia( x + 1 , y + 1 ) ]++;
    if( j != m ) addedge( hernia( i , j ) , hernia( i , j + 1 ) , inf ) , in[ hernia( i , j ) ]++;
    }
    topo();
    for( register int i = 1 ; i <= n ; i++ )
    for( register int j = 1 ; j <= m ; j++ )
    if( vis[ hernia( i , j ) ] && a[i][j] > 0 ) ans += a[i][j];
    while( bfs() ) while( temp = dinic( s , inf ) ) ans -= temp;
    cout << ans << endl;
    return 0;
    }

  • 0
    @ 2015-05-03 20:18:26

    #include<iostream>
    #include<fstream>
    #include<cstdio>
    #include<stdio.h>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<queue>

    #define fin cin
    #define fout cout

    using namespace std;

    //ifstream fin("pvz.in");
    //ofstream fout("pvz.out");
    struct edge
    {
    int xb;
    edge* next;
    };
    struct lian
    {
    edge* link;
    };

    struct bian
    {
    int ux,uy,vx,vy,c,f;
    };

    struct node
    {
    int nx,ny;
    node* next;
    };

    struct topology
    {
    int data;
    node* link;
    };

    int n,m;

    int score[60][60];
    lian* g[60][60];
    int px,py;
    int attack;
    int sum;
    bool pan[60][60];
    bian hu[100000];
    edge* p;
    topology* k1[60][60];
    node* s;
    queue<int> ax;
    queue<int> ay;

    int dist[60][60];

    int min(int shu1,int shu2)
    {
    if (shu1<shu2)
    return shu1;
    else
    return shu2;
    }

    /*void bfs2(int sx,int sy)
    {
    memset(pan2,false,sizeof(pan2));
    while(!ax.empty())
    ax.pop();
    while(!ay.empty())
    ay.pop();
    ax.push(sx);
    ay.push(sy);
    pan2[sx][sy]=true;

    while(!ax.empty())
    {
    int zx=ax.front();
    int zy=ay.front();
    ax.pop();
    ay.pop();
    p=g[zx][zy]->link;
    while (p!=NULL)
    {
    int hx=hu[p->xb].vx;
    int hy=hu[p->xb].vy;
    if (p->xb%2==1&&pan2[hx][hy]==false&&pan[hx][hy]&&hu[p->xb].c-hu[p->xb].f>0)
    {
    pan2[hx][hy]=true;
    ax.push(hx);
    ay.push(hy);
    }
    p=p->next;
    }

    }

    }
    */
    bool bfs(int sx,int sy)
    {
    while(!ax.empty())
    ax.pop();
    while(!ay.empty())
    ay.pop();
    ax.push(sx);
    ay.push(sy);
    for(int i=0;i<n;i++)
    for (int j=0;j<m;j++)
    dist[i][j]=1000000;
    dist[n][m+1]=1000000;
    dist[sx][sy]=0;
    while(!ax.empty())
    {
    int zx=ax.front();
    int zy=ay.front();
    ax.pop();
    ay.pop();
    p=g[zx][zy]->link;
    while (p!=NULL)
    {
    int hx=hu[p->xb].vx;
    int hy=hu[p->xb].vy;
    if (dist[hx][hy]==1000000&&pan[hx][hy]&&hu[p->xb].c-hu[p->xb].f>0)
    {
    dist[hx][hy]=dist[zx][zy]+1;
    //fout<<hx<<' '<<hy<<' '<<p->xb<<endl;
    ax.push(hx);
    ay.push(hy);
    }
    p=p->next;
    }
    if (dist[n][m+1]!=1000000)
    return true;
    }
    if (dist[n][m+1]!=1000000)
    return true;
    else
    return false;
    }

    int dfs(int xx,int xy,int mina)
    {
    if ((xx==n&&xy==m+1)||mina==0)
    return mina;
    int flow=0;
    edge* p1=g[xx][xy]->link;
    while (p1!=NULL)
    {
    int hx=hu[p1->xb].vx;
    int hy=hu[p1->xb].vy;
    int hxb=p1->xb;
    if (dist[hx][hy]==dist[xx][xy]+1&&hu[hxb].c-hu[hxb].f>0)
    {
    int re=dfs(hx,hy,min(mina,hu[hxb].c-hu[hxb].f));
    flow+=re;
    hu[hxb].f+=re;
    if (hxb%2==0)
    hu[hxb-1].f+=-re;
    else
    hu[hxb+1].f+=-re;
    mina+=-re;
    if (mina==0) break;
    }
    p1=p1->next;
    }
    return flow;
    }

    int main()
    {
    fin>>n>>m;
    for (int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
    g[i][j]=new lian;
    g[i][j]->link=NULL;
    }
    g[n+1][m]=new lian;
    g[n+1][m]->link=NULL;
    g[n][m+1]=new lian;
    g[n][m+1]->link=NULL;

    for (int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
    k1[i][j]=new topology;
    k1[i][j]->link=NULL;
    k1[i][j]->data=0;
    }
    sum=0;

    for (int i=0;i<n;i++)
    {
    for (int j=0;j<m;j++)
    {
    fin>>score[i][j];
    {
    if (score[i][j]>0)
    {
    sum++;
    hu[sum].ux=n+1;
    hu[sum].uy=m;
    hu[sum].vx=i;
    hu[sum].vy=j;
    hu[sum].c=score[i][j];
    hu[sum].f=0;
    p=new edge;
    p->next=g[n+1][m]->link;
    g[n+1][m]->link=p;
    p->xb=sum;

    sum++;
    hu[sum].ux=i;
    hu[sum].uy=j;
    hu[sum].vx=n+1;
    hu[sum].vy=m;
    hu[sum].c=score[i][j];
    hu[sum].f=score[i][j];
    p=new edge;
    p->next=g[i][j]->link;
    g[i][j]->link=p;
    p->xb=sum;

    }

    else
    {
    sum++;
    hu[sum].ux=i;
    hu[sum].uy=j;
    hu[sum].vx=n;
    hu[sum].vy=m+1;
    hu[sum].c=-score[i][j];
    hu[sum].f=0;
    p=new edge;
    p->next=g[i][j]->link;
    g[i][j]->link=p;
    p->xb=sum;

    sum++;
    hu[sum].ux=n;
    hu[sum].uy=m+1;
    hu[sum].vx=i;
    hu[sum].vy=j;
    hu[sum].c=-score[i][j];
    hu[sum].f=-score[i][j];
    p=new edge;
    p->next=g[n][m+1]->link;
    g[n][m+1]->link=p;
    p->xb=sum;
    }
    }
    fin>>attack;
    for (int k=1;k<=attack;k++)
    {
    fin>>px>>py;

    sum++;
    hu[sum].ux=px;
    hu[sum].uy=py;
    hu[sum].vx=i;
    hu[sum].vy=j;
    hu[sum].c=1000000;
    hu[sum].f=0;
    p=new edge;
    p->next=g[px][py]->link;
    g[px][py]->link=p;
    p->xb=sum;

    sum++;
    hu[sum].ux=i;
    hu[sum].uy=j;
    hu[sum].vx=px;
    hu[sum].vy=py;
    hu[sum].c=1000000;
    hu[sum].f=1000000;
    p=new edge;
    p->next=g[i][j]->link;
    g[i][j]->link=p;
    p->xb=sum;

    s=new node;
    s->next=k1[i][j]->link;
    k1[i][j]->link=s;
    s->nx=px;
    s->ny=py;
    k1[px][py]->data+=1;
    }
    if (j!=0)
    {
    sum++;
    hu[sum].ux=i;
    hu[sum].uy=j-1;
    hu[sum].vx=i;
    hu[sum].vy=j;
    hu[sum].c=1000000;
    hu[sum].f=0;
    p=new edge;
    p->next=g[i][j-1]->link;
    g[i][j-1]->link=p;
    p->xb=sum;

    sum++;
    hu[sum].ux=i;
    hu[sum].uy=j;
    hu[sum].vx=i;
    hu[sum].vy=j-1;
    hu[sum].c=1000000;
    hu[sum].f=1000000;
    p=new edge;
    p->next=g[i][j]->link;
    g[i][j]->link=p;
    p->xb=sum;

    s=new node;
    s->next=k1[i][j]->link;
    k1[i][j]->link=s;
    s->nx=i;
    s->ny=j-1;
    k1[i][j-1]->data+=1;
    }
    }
    }
    memset(pan,false,sizeof(pan));
    bool panding=true;
    while (panding)
    {
    panding=false;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    if (k1[i][j]->data==0&&pan[i][j]==false)
    {
    pan[i][j]=true;
    s=k1[i][j]->link;
    while (s!=NULL)
    {
    k1[s->nx][s->ny]->data+=-1;
    s=s->next;
    }
    panding=true;
    }
    }
    pan[n+1][m]=true;
    pan[n][m+1]=true;
    /*for (int i=1;i<=sum;i++)
    {
    if (i<10)
    fout<<'0';
    fout<<i<<' '<<hu[i].ux<<' '<<hu[i].uy<<' '<<hu[i].vx<<' '<<hu[i].vy<<' '<<hu[i].c<<' '<<endl;
    }
    fout<<endl;
    for (int i=0;i<n;i++)
    for (int j=0;j<m;j++)
    {
    fout<<i<<' '<<j<<' ';
    p=g[i][j]->link;
    while (p!=NULL)
    {
    fout<<p->xb<<' ';
    p=p->next;
    }
    fout<<endl;
    }
    fout<<n+1<<' '<<m<<' ';
    p=g[n+1][m]->link;
    while (p!=NULL)
    {
    fout<<p->xb<<' ';
    p=p->next;
    }
    fout<<endl;
    fout<<n<<' '<<m+1<<' ';
    p=g[n][m+1]->link;
    while (p!=NULL)
    {
    fout<<p->xb<<' ';
    p=p->next;
    }
    fout<<endl;
    fout<<endl;
    for(int i=0;i<n;i++)
    {
    for(int j=0;j<m;j++)
    fout<<pan[i][j]<<' ';
    fout<<endl;
    }*/
    int maxflow=0;

    while(bfs(n+1,m))
    {
    /*fout<<endl;
    for (int i=0;i<n;i++)
    {
    for (int j=0;j<m;j++)
    fout<<dist[i][j]<<' ';
    fout<<endl;
    }
    fout<<dist[n+1][m]<<' '<<dist[n][m+1]<<endl;*/

    maxflow+=dfs(n+1,m,1000000);

    /*for (int i=1;i<=sum;i++)
    {
    if (i<10)
    fout<<'0';
    fout<<i<<' '<<hu[i].ux<<' '<<hu[i].uy<<' '<<hu[i].vx<<' '<<hu[i].vy<<' '<<hu[i].c<<' '<<hu[i].f<<endl;
    }
    fout<<endl;
    fout<<maxflow<<endl;*/
    }

    /*for (int i=0;i<n;i++)
    {
    for (int j=0;j<m;j++)
    fout<<dist[i][j]<<' ';
    fout<<endl;
    }
    fout<<dist[n+1][m]<<' '<<dist[n][m+1]<<endl;
    */

    /*for (int i=1;i<=sum;i++)
    {
    if (i<10)
    fout<<'0';
    fout<<i<<' '<<hu[i].ux<<' '<<hu[i].uy<<' '<<hu[i].vx<<' '<<hu[i].vy<<' '<<hu[i].c<<' '<<hu[i].f<<endl;
    }*/

    /*bfs2(n+1,m);*/

    int maxsum=0;
    for (int i=0;i<n;i++)
    for (int j=0;j<m;j++)
    if (pan[i][j]&&score[i][j]>0)
    {
    maxsum+=score[i][j];
    }

    //fout<<endl;
    fout<<maxsum-maxflow<<endl;

    /*for (int i=0;i<n;i++)
    {
    for (int j=0;j<m;j++)
    fout<<pan2[i][j]<<' ';
    fout<<endl;
    }*/
    return 0;
    }

    我的代码风格有点**,但求教为何第9个点会访问无效内存。

    测试数据 #0: Accepted, time = 0 ms, mem = 2676 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 2676 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 2676 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 2680 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 2696 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 2728 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 2776 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 2768 KiB, score = 10
    测试数据 #8: RuntimeError, time = 375 ms, mem = 7816 KiB, score = 0
    测试数据 #9: Accepted, time = 15 ms, mem = 2832 KiB, score = 10
    RuntimeError, time = 435 ms, mem = 7816 KiB, score = 90

  • 0
    @ 2014-01-01 16:21:24

    最小割模型,建图,然后先用Tarjan算法求强连通分量,如果该SCC的大小>1,将其中的点往汇点连一无穷大的边,然后最大流之:
    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 532 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 548 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 544 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 556 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 588 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 616 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 612 KiB, score = 10
    测试数据 #8: Accepted, time = 765 ms, mem = 12028 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 652 KiB, score = 10
    Accepted, time = 795 ms, mem = 12028 KiB, score = 100

    http://hi.baidu.com/greencloud/item/c0d26c901a78a0d71f4271f0

  • 0
    @ 2010-04-02 17:39:12

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    网络流求最大权闭合子图

    不难

    ……

    写tajian(无视我的拼写)

    累死人……

    ……

    自己还是弱的要死

    var tou,h,vh,p,low,dfn,zhan,belong:array[0..1000]of longint;

    g,wn,next,tt:array[0..1000000]of longint;

    yy,cnc,m,n,i,j,liu,ans,z,t,ii,jj,t_t,t__t,cnt,tt1,zz,x,y,ans1:longint;

    use:array[0..1000]of boolean;

    uu:array[0..1000]of longint;

    f:array[0..1000]of longint;

    find:boolean;

    procedure zuo(x:longint);

    var tmp,minh,xx:longint;

    begin

    if x=m*n+1 then

    begin

    find:=true;

    ans:=ans+liu;

    exit;

    end;

    minh:=m*n+1;

    tmp:=liu;

    xx:=tou[x];

    while xx-1 do

    begin

    if (g[xx]>0)and(uu[wn[xx]]=1)then

    begin

    if h[wn[xx]]+1=h[x] then

    begin

    if liu>g[xx] then liu:=g[xx];

    zuo(wn[xx]);

    if h[0]>=m*n+2 then exit;

    if find then break;

    liu:=tmp;

    end;

    if minh>h[wn[xx]] then minh:=h[wn[xx]];

    end;

    xx:=next[xx];

    end;

    if find then

    begin

    g[xx]:=g[xx]-liu;

    yy:=xx;

    g[xx+tt[xx]]:=g[xx+tt[xx]]+liu;

    end

    else

    begin

    dec(vh[h[x]]);

    if vh[h[x]]=0 then begin h[0]:=m*n+2;exit; end;

    h[x]:=minh+1;

    inc(vh[h[x]]);

    end;

    end;

    procedure add(x,y,z:longint);

    begin

    t:=t+1;

    wn[t]:=y;

    tt[t]:=1;

    g[t]:=z;

    next[t]:=tou[x];

    tou[x]:=t;

    t:=t+1;

    wn[t]:=x;

    tt[t]:=-1;

    g[t]:=0;

    next[t]:=tou[y];

    tou[y]:=t;

    end;

    procedure work(x:longint);

    var xx,j:longint;

    begin

    tt1:=tt1+1;

    dfn[x]:=tt1;

    low[x]:=tt1;

    use[x]:=true;

    zz:=zz+1;

    zhan[zz]:=x;

    xx:=tou[x];

    while xx-1 do

    begin

    if g[xx]0 then

    begin

    j:=wn[xx];

    if dfn[j]=0 then

    begin

    work(j);

    if low[j]0) then ans1:=ans1+p[i];

    vh[0]:=m*n+2;

    while h[0]

  • 0
    @ 2010-03-03 18:58:36

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    模型,套之

    最大权闭合图模型

  • 0
    @ 2010-03-03 16:33:06

    话说我不会写搜索判环- -|||

    于是Floyd出场......

    于是时间....

    编译通过...

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

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

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

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

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

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

    ├ 测试数据 07:答案正确... 321ms

    ├ 测试数据 08:答案正确... 243ms

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

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

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

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

    另:我写的是SAP+断层优化,邻接表还加了当前弧优化,然后第9个点跑了100s超时......但是用二维数组存流量就AC了....话说这是一件很神奇的事...

  • 0
    @ 2009-11-09 16:14:34

    orz

    orz

    orz

    orz

  • 0
    @ 2009-11-08 16:13:26

    这款游戏还是挺好玩的。

    但是。。。。这道题就有点BT了

  • 0
    @ 2009-10-18 21:47:09

    写了三个dfs,就过了.

    建模至今不会证明......

    建模如下:

    对于强联通分量(大于1),连一条到T的边,无穷大容量

    对于每个点,连一条到它左边的点的边,无穷大容量

    对于每个点,连一条到能够保护它的点的边,无穷大容量

    对于每个正点,从S连一条到它的边,容量为这个点的权值

    对于每个负点,连一条到T的边,这个点权值的相反数作为容量

    求S-T最大流。

    ans = sigma(所有正点) - 最大流.

    话说这个题我怎么搞不到0ms....我只能到72ms = =|||

  • 0
    @ 2009-09-10 21:46:41

    看到题就晕了...

  • 0
    @ 2009-09-09 14:54:36

    把g打成j,居然还能过9个数据。。。。。。

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-09-07 13:08:00

    一起摇滚吧....#

  • 0
    @ 2009-09-09 12:29:10

    第一遍交,70分。。

    我找强连通用了2个dfs,然后找强连通分量连向的点用了1个dfs。

    结果第3个dfs中递归调用了第2个dfs。。。郁闷(这样也能70,我很疑惑。。)

    改了后交,90分。。

    第9个点超,于是交了个输出总边数的程序(不能算骗数据吧。。),发现14多万。。

    数组改到300万(刚开始以为140多万...),第三次交,就是下面的情况。。

    编译通过...

  • 0
    @ 2009-08-28 17:52:19

    找环是关键,找环的效率决定了程序的效率。

    要是当时NOI的时候我会做这题就好了!

  • 0
    @ 2009-08-28 17:38:38

    编译通过...

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

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

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

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

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

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

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

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

    ├ 测试数据 09:运行超时...

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

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

    Unaccepted 有效得分:90 有效耗时:0ms

    晕~~

  • 0
    @ 2009-08-25 10:43:34

    There is a zombie on your lawn

  • 0
    @ 2009-09-12 17:16:55

    把原图抽象成n*m个点,然后若i控制j,则j->i,然后每个点连接向原图中在他右边的点,求该图类最大密闭子图。

    类最大密闭子图指:给定带权有向图,选出点集,使得点集内任意点i所指向的点j在点集内出现,且点集权和最大,且选出点集在原图内无环。

    解法是这样:首先拓扑排序出在环上且能到环上的点集合V1,然后,对于每一个节点来说,如果这个节点的权值为正,则将其与源连接一条边,否则将其与汇连接一条边,边的容量就是节点权值的绝对值。然后,如果一个点在V1内,将其与汇连接一条边,权值为正无穷;如果节点A能够控制节点B,则连接B到A的有向边,权值为正无穷。求取这个网络流模型的最小割(最大流),然后用所有正权节点的和减去这个值,就是最后的答案。

    证明:最优方案一定不包括V1中的点,然后ans=正权的点的和-没选出来的正权点的和-选出来的负权点的绝对值。所以问题变成找出可行方案使得没选出来的正权点的和+出来的负权点的绝对值,然后再考虑该问题的最优方案,可以对应为上图的一个割,然后考虑该图的最小割,若存在边i->j而i->t,s->j,那么必定有k->i且s->k,j->q且q->t,则该方案不是割,所以最小割是一个可行方案

    要注意如果(i,j)控制(i,j-1)那么入度不要算两次

信息

ID
1607
难度
5
分类
图结构 | 网络流图结构 | 强连通分量 点击显示
标签
递交数
616
已通过
202
通过率
33%
被复制
2
上传者