作者存档：edward_mj

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1976

【算法分析】

这题是膜拜了解题报告才会得。

我只想说。。。我被虐到泪流满面

然后我来复述BT的解题报告。

首先，如果用bfs黑白交替染色，会发现每个点只会有一种颜色。（实际上就是到左上角那个点的哈密顿距离的奇偶性）

然后我们把奇点放左边，偶点放右边。

我们再定义：只有正能量的水晶能放出能量，而放出的能量就是它附近的负水晶个数。

这样。我们就可以利用一个最小割模型来求解。

我们想假设所有的点都是P点，并且他能放出最多的能量。（就是他放出和他相邻的格子数的能量）

然后就开始BT了。。。

定义：对于一个割，

如果奇点被割到和源相连的那一边。那么算是P，否则算是N。

如果偶点被割到和汇相连的那一边。那么算是P，否则算是N。

然后对应地。

我们连边S->奇点，容量为该奇点相邻点的个数。

连边偶点->T，容量为该偶点相邻点的个数。（其实除了边界，都是6）

然后对于相邻的奇偶两点，连边 奇点->偶点，容量为2。

这样连的理由是。

如果S->奇点的边成为割边，那么该奇点就变成N了。那么将不再放出能量。所以减去属于他放出的能量。

如果偶点->T的边成为割边，那么该偶点就变成N了。那么也不再放出能量。所以减去属于他放出的能量。

如果奇点->偶点的边成为割边，那么必然（奇点属于S集）（偶点属于T集） 【否则怎么叫割边。。。】

那么就是这个奇点和那个偶点都同时成为了P。那么他们放出的能量都要减1。一共减2。

原因是：本来假设相邻的点都是N，所以当成可以放出全部能量，但是因为相邻的这个不是N。所以大家放出的能量都要减~

所以最后的答案就是：每个点的相邻格子数之和减去最小割。

【其它】

感叹一句：太imba了。

我写的sap再次过不了。。。难道又疵了。。。

改成dinic才过。。。

另外强力膜拜75MS的tracyhenry大神。

【CODE】

#include

#include

#include #include using namespace std;
const int N=40;
const int INF=1000000000;
int n,Sum;
int pos[N][N][N];
char map[N][N][N];
bool odd[N][N][N];
struct edge{int x,y,c;edge *next,*op;};
struct Network_t{
       edge g[1000000],*ls[100000],*cur[100000];
       int vs,vt,d[100000],Flow,Q[100000],e;
      
       void addedge(int x,int y,int c){
            g[++e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
            g[++e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
       }
      
       int dfs(int p,int nf){
           if (p==vt) return nf;
           int tmp,FF=0;
           for (edge *&t=cur[p];t;t=t->next)
             if (t->c && d[t->x]+1==d[t->y] && (tmp=dfs(t->y,min(nf,t->c)))){
               FF+=tmp;
               t->c-=tmp; t->op->c+=tmp;
               if (!(nf-=tmp)) break;
             }
           if (!cur[p]) d[p]=INF;
           return FF;
       }
      
       bool bfs(){
            for (int i=vs;i<=vt;i++){
                d[i]=INF;
                cur[i]=ls[i];
            }
            d[vs]=1; Q[1]=vs;
            for (int st=1,ed=1;d[Q[st]]              for (edge *t=ls[Q[st]];t;t=t->next)
                if (t->c && d[t->y]==INF) d[ Q[++ed]=t->y ]=d[t->x]+1;
            if (d[vt]==INF) return false;
            return true;
       }
      
       void dinic(){
            Flow=0;
            int tmp;
            while (bfs())
              while (tmp=dfs(vs,INF)) Flow+=tmp;
       }
}Network;

bool flag(int x,int y,int z){return (0<=x && xvoid init(){
     scanf("%d",&n);
     int i,j,k,cnt=0;
     char ch;
     for (k=0;k       for (i=0;i         for (j=0;j             ch=getchar();
             while (ch==’ ‘ || ch==’n’) ch=getchar();
             map[k][i][j]=ch;
             pos[k][i][j]=++cnt;
             if (!i && !j) odd[k][i][j]=k%2; else
             if (!i) odd[k][i][j]=!odd[k][i][j-1]; else
             odd[k][i][j]=!odd[k][i-1][j];
         }
     Network.vs=0; Network.vt=++cnt;
     for (k=0;k       for (i=0;i         for (j=0;j             cnt=0;
             if (flag(k-1,i,j)) cnt++;
             if (flag(k+1,i,j)) cnt++;
             if (flag(k,i-1,j)) cnt++;
             if (flag(k,i+1,j)) cnt++;
             if (flag(k,i,j-1)) cnt++;
             if (flag(k,i,j+1)) cnt++;
             Sum+=cnt;
             if (odd[k][i][j]){
               Network.addedge(Network.vs,pos[k][i][j],cnt);
               switch (map[k][i][j]){
                 case ‘P’:Network.addedge(Network.vs,pos[k][i][j],INF); break;
                 case ‘N’:Network.addedge(pos[k][i][j],Network.vt,INF); break;
               }
               if (flag(k-1,i,j)) Network.addedge(pos[k][i][j],pos[k-1][i][j],2);
               if (flag(k+1,i,j)) Network.addedge(pos[k][i][j],pos[k+1][i][j],2);
               if (flag(k,i-1,j)) Network.addedge(pos[k][i][j],pos[k][i-1][j],2);
               if (flag(k,i+1,j)) Network.addedge(pos[k][i][j],pos[k][i+1][j],2);
               if (flag(k,i,j-1)) Network.addedge(pos[k][i][j],pos[k][i][j-1],2);
               if (flag(k,i,j+1)) Network.addedge(pos[k][i][j],pos[k][i][j+1],2);
             }else{
               Network.addedge(pos[k][i][j],Network.vt,cnt);
               switch (map[k][i][j]){
                 case ‘P’:Network.addedge(pos[k][i][j],Network.vt,INF); break;
                 case ‘N’:Network.addedge(Network.vs,pos[k][i][j],INF); break;
               }
             }
         }
}

int main(){
    init();
    Network.dinic();
    printf("%dn",Sum-Network.Flow);
    return 0;
}

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1977

【算法分析】

这道题本应该倍增的方法也应该可以AC得，但是时间卡得太紧。。。无奈TLE。

先说这种AC的算法吧。

1、先用kruskal进行MST。

2、如果尝试用一条边去搞进去的话，那么就要求对应两点中那条树链中的最大权边或者次大权边，才能知道假如包含这条边的严格次小生成树是多大。

AC的算法是这么实现的。

这种方法来源于：http://hi.baidu.com/wjbzbmr/blog/item/c3c8ff0455e3c87003088121.html

在求LCA的Tarjan算法中，我们利用并差集和DFS序实现，实际上在用并差集维护的时候，可以同时维护出到当前子树根的树链上的最大/次大权边。其实如果有比较深刻的体会的话，不难实现。

第二种算法(TLE)

在实现第二步的时候，使用倍增思想。

Fp[i][j]表示i这个结点，向上2^j个父亲，是谁。

FL[i][j][0..1]表示i这个结点，到向上2^j个父亲这条树链上，最大值和次大值分别是多少。

我们定义根的结点为其本身，那么就可以类似RMQ地求出这两个数组。

求他的复杂度为O(n lg n)。

然后每次询问(x,y)的时候，我们只要知道Lca(x,y)，然后利用2^k步长的类似爬山的走法。就可以达到每次询问，回答的复杂度是O(n lg n)

第三种算法。

用树链剖分去解。。。但是第二种常数比较小的都A不了。。。这个就不用看了= =

【其它】

泪流满面，这么多天了，终于AC。

另外我的C++代码是算法二的，提交显示TLE，但利用批处理经过随机大量大小数据，答案与AC程序是一致的。。。

然后我之所以用Pascal，是因为C++可能要爆栈。。。所以要手写栈。

而Pascal能用编译开关调栈~= =

【CODE】【Pascal】【算法一】【AC】

{$M 10000000}
{$inline on}
const
inf=’input.txt’;
ouf=’output.txt’;
max_num=1000000000;

type
gtp=record
        y,w,zz,next:longint;
      end;
arr=array [0..1] of longint;
node=record
         x,y,w:longint;
         res:arr;
         used:boolean;
       end;

var
n,m,e,qe,lca_e:longint;
mstw:int64;
g:array [0..205555] of gtp;
qg,lca_g:array [0..605555] of gtp;
data:array [1..300000] of node;
Q,v,f,ls,qls,lca_ls:array [1..100000] of longint;
d:array [1..100000] of arr;

procedure init;
var
i:longint;
begin
e:=1; qe:=1;
read(n,m);
for i:=1 to m do
    with data[i] do
      begin
        read(x,y,w);
        used:=false;
        res[0]:=-max_num;
        res[1]:=-max_num;
      end;
for i:=1 to n do
    begin
      d[i,0]:=-max_num;
      d[i,1]:=-max_num;
    end;
end;

procedure sort(l,r:longint);
var
i,j,mid:longint;
tmp:node;
begin
if l>=r then exit;
mid:=data[(l+r) div 2].w;
i:=l; j:=r;
repeat
    while data[i].w    while data[j].w>mid do dec(j);
    if i<=j then
      begin
        tmp:=data[i]; data[i]:=data[j]; data[j]:=tmp;
        inc(i); dec(j);
      end;
until i>j;
sort(l,j);
sort(i,r);
end;

procedure addedge(x,y,w:longint);
begin
inc(e);
g[e].y:=y; g[e].next:=ls[x]; ls[x]:=e; g[e].w:=w;
end;

function gf(k:longint):longint;
begin
if f[k]=k then exit(k);
f[k]:=gf(f[k]);
exit(f[k]);
end;

procedure MST;
var
i,times:longint;
begin
times:=0;
for i:=1 to n do f[i]:=i;
for i:=1 to m do
    with data[i] do
      if gf(x)<>gf(y) then
        begin
          f[f[x]]:=f[y];
          used:=true;
          addedge(x,y,w);
          addedge(y,x,w);
          inc(MSTw,w);
          inc(times);
        end;
i:=4;
end;

procedure addq(x,y:longint);
begin
inc(qe);
qg[qe].y:=y; qg[qe].next:=qls[x]; qls[x]:=qe;
end;

procedure build;
var
i,j:longint;
begin
for i:=1 to m do
    with data[i] do
      begin
        addq(x,y);
        qg[qe].zz:=i;
        addq(y,x);
        qg[qe].zz:=i;
      end;
end;

procedure Add_Lca_Link(p,y:longint); inline;
begin
inc(lca_e);
lca_g[lca_e].y:=y;
lca_g[lca_e].next:=lca_ls[p];
lca_ls[p]:=lca_e;
end;

procedure push(var res:arr;w:longint); inline;
begin
if w=res[0] then exit;
if w>res[0] then
    begin
      res[1]:=res[0];
      res[0]:=w;
      exit;
    end;
if w>res[1] then res[1]:=w;
end;

procedure union(k:longint);
var
i,root,tmp,Qt:longint;
res:arr;
begin
i:=k;
Qt:=0;
res[0]:=-max_num;
res[1]:=-max_num;
while f[i]<>i do
    begin
      inc(Qt);
      Q[Qt]:=i;
      i:=f[i];
    end;
inc(Qt);
Q[Qt]:=i;
for i:=Qt downto 1 do
    begin
      push(d[Q[i]],res[0]);
      push(d[Q[i]],res[1]);
      push(res,d[Q[i]][0]);
      push(res,d[Q[i]][1]);
      f[Q[i]]:=Q[Qt];
    end;
end;

procedure dfs(p,fa,w:longint);
var
t:longint;
begin
t:=ls[p];
while t>0 do
    begin
      if g[t].y<>fa then
        dfs(g[t].y,p,g[t].w);
      t:=g[t].next;
    end;

t:=qls[p];
while t>0 do
    with qg[t] do
      begin
        if v[y]=1 then
          begin
            union(y);
            Add_Lca_Link(f[y],zz);
          end;
        t:=next;
      end;

t:=lca_ls[p];
while t>0 do
    with lca_g[t] do
      begin
        union(data[y].x); union(data[y].y);
        push(data[y].res,d[data[y].x,0]);
        push(data[y].res,d[data[y].x,1]);
        push(data[y].res,d[data[y].y,0]);
        push(data[y].res,d[data[y].y,1]);
        t:=next;
      end;

f[p]:=fa;
push(d[p],w);
v[p]:=1;
end;

procedure Tarjan;
var
i,j:longint;
begin
for i:=1 to n do f[i]:=i;
dfs(1,1,-max_num);
end;

function min(x,y:int64):int64;
begin
if x         else min:=y;
end;

procedure solve;
var
i:longint;
ans:int64;
begin
ans:=int64(maxlongint)*int64(maxlongint);
for i:=1 to m do
    if not data[i].used then
      begin
        if data[i].res[0]=-max_num then data[i].res[0]:=0;
        if data[i].res[0]<>data[i].w then
          ans:=min(ans,MSTw-data[i].res[0]+data[i].w)
        else if data[i].res[1]<>-max_num then
          ans:=min(ans,MSTw-data[i].res[1]+data[i].w);
      end;
writeln(ans);
end;

begin
init;
sort(1,m);
MST;
build;
Tarjan;
solve;
end.

【CODE】【C++】【算法二（倍增）】【TLE】

#include #define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
const int N=100005;
const int E=300005;
const int INF=1000000000;
const int LgN=20;
typedef __int64 lld;
struct edge{int x,y,w,next;}g[N*2];
int n,m,e,Qt;
lld MSTw;
int ls[N],F[N],FL[N][LgN][2],Fp[N][LgN],List[N],depth[N],fa[N],QL[N*2],R[N],LCA[N*2][LgN];
int Lg[N];
struct data{int x,y,w;bool used;}L[E];
inline int cmp(const void *A,const void *B){return ((data*)A)->w-((data*)B)->w;}

void Read(int &x){
     char ch=getchar();
    
}

inline void init(){
     scanf("%d%d",&n,&m);
     for (int i=1;i<=m;i++){
       scanf("%d%d%d",&L[i].x,&L[i].y,&L[i].w);
       L[i].used=false;
     }
}

inline void addedge(int x,int y,int w){
     g[++e].x=x; g[e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=e;
     g[++e].x=y; g[e].y=x; g[e].w=w; g[e].next=ls[y]; ls[y]=e;
}

inline int GF(int v){
    int res,i,tmp;
    for (i=v;F[i]!=i;i=F[i]);
    res=i;
    for (i=v;F[i]!=i;tmp=F[i],F[i]=res,i=tmp);
    return res;
}

inline void MST(){
     e=1; memset(ls,0,sizeof(ls));
     MSTw=0;
     int tt=n;
     for (int i=1;i<=n;i++) F[i]=i;
     for (int i=1;i<=m;i++)
       if (GF(L[i].x)!=GF(L[i].y)){
         L[i].used=true;
         addedge(L[i].x,L[i].y,L[i].w);
         F[F[L[i].x]]=F[L[i].y];
         MSTw+=L[i].w;
         tt–;
         if (tt==1) break;
       }
     return;
}

inline void bfs(){
     fa[1]=0;
     int head=0,tail=1,x,y;
     List[1]=1; depth[1]=1;
     while (head!=tail){
           head++;
           for (int t=ls[List[head]];t;t=g[t].next){
               x=g[t].x; y=g[t].y;
               if (t!=(fa[x]^1)){
                 List[++tail]=y;
                 fa[y]=t;
                 depth[y]=depth[x]+1;
               }
           }
     }
}

int stack,t[N],v[N];
inline void Hand_Write_Dfs(){
     int i,y;
     for (i=1;i<=n;i++) t[i]=ls[i];
     List[1]=stack=v[1]=R[1]=Qt=QL[1]=1;
     while (stack){
          if (!t[List[stack]])
            stack–;
          else{
            int &tt=t[List[stack]];
            if (tt!=ls[List[stack]]) QL[++Qt]=List[stack];
            y=g[tt].y;
            tt=g[tt].next;
            if (!v[y]){
              List[++stack]=y;
              v[y]=1;
              QL[++Qt]=y;
              R[y]=Qt;
            }
          }
     }
}

inline void Make_LCA(){
     int i,k,s;
     for (i=1;i<=Qt;i++) LCA[i][0]=QL[i];
     for (k=1;1<       s=1<<(k-1);
       for (i=1;i+(1<         if (depth[LCA[i][k-1]]           LCA[i][k]=LCA[i][k-1];
         else
           LCA[i][k]=LCA[i+s][k-1];
     }
}

inline void Push(int *F1,int *F2){
       if (F2[0]>F1[0]) {F1[1]=F1[0]; F1[0]=F2[0];}else
       if (F2[0]>F1[1] && F2[0]!=F1[0]) F1[1]=F2[0];
       if (F2[1]>F1[0]) {F1[1]=F1[0]; F1[0]=F2[1];}else
       if (F2[1]>F1[1] && F2[1]!=F1[0]) F1[1]=F2[1];
}

inline void Make_Fa(){
     g[0].x=1; g[0].y=1; g[0].w=0;
     g[1].x=1; g[1].y=1; g[0].w=0;
     int i,k,s;
     for (i=1;i<=n;i++){
         FL[i][0][0]=g[fa[i]].w;
         FL[i][0][1]=-INF;
         Fp[i][0]=g[fa[i]].x;
     }
     for (k=1;1<       for (i=1;i<=n;i++){
           Fp[i][k]=Fp[Fp[i][k-1]][k-1];
           FL[i][k][0]=-INF;
           FL[i][k][1]=-INF;
           Push(FL[i][k],FL[i][k-1]);
           Push(FL[i][k],FL[Fp[i][k-1]][k-1]);
       }
}

inline void Make_Log(){
     Lg[1]=0;
     for (int i=2;i<=Qt;i++)
       if (1 << (Lg[i-1]+1)==i)
         Lg[i]=Lg[i-1]+1;
       else
         Lg[i]=Lg[i-1];
}

inline int Get_Lca(int l,int r){
    if (l>r){l^=r;r^=l;l^=r;}
    int k=Lg[r-l+1];
    if (depth[LCA[l][k]]      return LCA[l][k];
    else
      return LCA[r-(1<}

int res[2];
inline void Get_Max(int x,int y){
     int i,k=Lg[n];
     i=y;
     while (i!=x){
           while (depth[Fp[i][k]]           Push(res,FL[i][k]);
           i=Fp[i][k];
     }
}

inline void solve(){
     int i,Lca;
     lld ans=(lld)(1) << 60;
     for (i=1;i<=m;i++)
       if (!L[i].used){
         Lca=Get_Lca(R[L[i].x],R[L[i].y]);
         res[0]=-INF;
         res[1]=-INF;
         Get_Max(Lca,L[i].x);
         Get_Max(Lca,L[i].y);
         if (res[0]!=L[i].w)
           ans=min(ans,MSTw-res[0]+L[i].w);
         else if (res[1]!=-INF)
           ans=min(ans,MSTw-res[1]+L[i].w);
       }
     printf("%I64dn",ans);
}

int main(){
    init();
    qsort(L+1,m,sizeof(data),cmp);
    MST();
    bfs();
    Hand_Write_Dfs();
    Make_LCA();
    Make_Fa();
    Make_Log();
    solve();
    return 0;
}

【题目链接】

http://ace.delos.com/ioiupload?init=1&a=nejLCFTaRn6

http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1779

【题目大意】

有n个点，m条边的无向图。

上面的点一开始要么是J牛，要么是T牛，要么是E，表示没有牛。

然后J牛有两种选择：

1、直接攻击自己附近的一只T牛，然后停住永远不动。

2、向邻近的点走一步，然后攻击or不攻击附近的一只T牛，然后停住永远不动。

特别得，

J牛不能跑进任何一只本身有牛的点。

T牛不会动。并且只能被打死一次。然后就算他死了，J牛也不能进入他的领土（他的灵魂开无敌了）!!!

然后他们动都有先后顺序，然后问最多能打死多少只T牛。

【算法分析】

建立一个4层的图。

第一层，给每只J牛赋予1的流量。

第二层，每只J牛要么停在原来这个点，要么走一步，到达另外一个点。

流量可以跟随这只牛的脚步走过去。

当然，到达的点不能是T牛占得点。

第三层，从第二层的对应点中引一条容量为1的边到第三层的对应点，那么就对应于：每个点只能有一只牛。

第四层，那些牛们“站位”已经到了最好状态，开始攻击T牛，即每个“非T牛”的点像每只T牛点连一个容量为1的边，然后T牛们就可以向汇点连容量为1的边。

这样，就完成了最终的匹配。

这个用最大流实现即可。输出方案利用残余图不难得出。当然，我写得是无方案版。

【CODE】

/*
ID:jie22221
TASK:cowwar
LANG:C++
*/
#include #include #include #define min(x,y) ((x)<(y)?(x):(y))
#define clr(a) memset(a,0,sizeof(a))
const int N=30000;
const int INF=1000000000;
struct edge{int x,y,c;edge *next,*op;};
struct Network_t{
       edge *ls[N],*cur[N];
       int vs,vt,d[N],Flow,Q[N];
      
       void addedge(int x,int y,int c){
            edge *p=(edge*)malloc(sizeof(edge));
            edge *q=(edge*)malloc(sizeof(edge));
            p->x=x; p->y=y; p->c=c; p->next=ls[x]; ls[x]=p; p->op=q;
            q->x=y; q->y=x; q->c=0; q->next=ls[y]; ls[y]=q; q->op=p;
       }
      
       int dfs(int p,int nf){
           if (p==vt) return nf;
           int tmp,FF=0;
           for (edge *&t=cur[p];t;t=t->next)
             if (t->c && d[t->x]+1==d[t->y] && (tmp=dfs(t->y,min(nf,t->c)))){
               FF+=tmp;
               t->c-=tmp; t->op->c+=tmp;
               if (!(nf-=tmp)) break;
             }
           if (!cur[p]) d[p]=INF;
           return FF;
       }
      
       bool bfs(){
            for (int i=0;i<=vt;i++){
                d[i]=INF;
                cur[i]=ls[i];
            }
            d[vs]=1; Q[1]=vs;
            for (int st=1,ed=1;d[Q[st]]              for (edge *t=ls[Q[st]];t;t=t->next)
                if (t->c && d[t->y]==INF) d[ Q[++ed]=t->y ]=d[t->x]+1;
            if (d[vt]==INF) return false;
            return true;
       }
      
       void dinic(){
            Flow=0;
            int tmp;
            while (bfs())
              while (tmp=dfs(vs,INF)) Flow+=tmp;
       }
}Network;
struct Node{int y;Node *next;};
struct Link_t{
       Node *ls[N];
       void addedge(int x,int y){
            Node *p=(Node*)malloc(sizeof(Node));
            p->y=y; p->next=ls[x]; ls[x]=p;
       }
}Link;

int n,m;
char str[N];

void init(){
     clr(Link.ls);
     clr(Network.ls);
     scanf("%d%d%s",&n,&m,str+1);
     for (int x,y,i=1;i<=m;i++){
         scanf("%d%d",&x,&y);
         Link.addedge(x,y);
         Link.addedge(y,x);
     }
}

void build(){
     Network.vs=0; Network.vt=n*4+1;
     for (int i=1;i<=n;i++){
       if (str[i]==’J’){
         Network.addedge(Network.vs,i,1);
         Network.addedge(i,n+i,1);
         for (Node *t=Link.ls[i];t;t=t->next)
           if (str[t->y]!=’T’)
             Network.addedge(i,n+t->y,1);
       }
       if (str[i]==’T’)
         Network.addedge(3*n+i,Network.vt,1);
       else{
         for (Node *t=Link.ls[i];t;t=t->next)
           if (str[t->y]==’T’)
             Network.addedge(2*n+i,3*n+t->y,1);
         Network.addedge(n+i,2*n+i,1);
       }
     }
}

int main(){
    freopen("cowwar.in","r",stdin);
    freopen("cowwar.out","w",stdout);
    init();
    build();
    Network.dinic();
    printf("%dn",Network.Flow);
}