http://www.cnblogs.com/abclzr/p/6635197.html

记录信息
评测状态 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;
}

http://www.cnblogs.com/JSZX11556/p/5154311.html

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

#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

最小割模型，建图，然后先用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

编译通过...

├ 测试数据 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]

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

模型，套之

最大权闭合图模型

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

于是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了....话说这是一件很神奇的事...

orz

orz

orz

orz

这款游戏还是挺好玩的。

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

写了三个dfs，就过了.

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

建模如下：

对于强联通分量（大于1），连一条到T的边，无穷大容量

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

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

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

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

求S-T最大流。

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

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

看到题就晕了...

把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

一起摇滚吧....#

第一遍交，70分。。

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

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

改了后交，90分。。

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

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

编译通过...

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

晕～～

There is a zombie on your lawn

把原图抽象成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)那么入度不要算两次