Eternity

Until The End

P1004 [NOIP2000 提高组] 方格取数 & P2045 方格取数加强版

发表于 分类于
本文字数： 3.6k 阅读时长 ≈ 3 分钟

一道 $\text{Dp}$ ，一道费用流。

原版

这道题是很早很早在 $\text{DCOI}$ 上贺的，后来进入洛谷之后有一个计划是刷完 $\text{P1000}\sim\text{P1050}$ ，即第一页（虽然现在都还没完成），而这道题是 $\text{P1004}$ ，所以就做了。

考虑把走两次转化为两人走，即两个人同时出发，走到终点的最大贡献，记录四维状态：

$Dp[x1][y1][x2][y2]$ 表示第一个人位置和第二个人位置的最大贡献，然后四维暴力转移，判重即可，时间复杂度 $\mathcal O(2^2n^4)$ ，可过。

码风是以前的码风，看不惯的话就……看不惯吧。

$\text{Update:}$ 重写了的，是现在的码风了，看不惯的话就没办法惹。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
const int MAXN=1e0+10;
const int dx[]={0,-1,0};
const int dy[]={0,0,-1};
int N,Mp[MAXN][MAXN],x,y,z;
int Dp[MAXN][MAXN][MAXN][MAXN];
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N);
    do
    {
        read(x,y,z);
        Mp[x][y]=z;
    }while(x||y||z);
    for(int i=1;i<=N;++i)
        for(int j=1;j<=N;++j)
            for(int k=1;k<=N;++k)
                for(int l=1;l<=N;++l)
                {
                    int Trans=0;
                    for(int k1=1;k1<=2;++k1)
                        for(int k2=1;k2<=2;++k2)
                        {
                            int nx1=i+dx[k1],ny1=j+dy[k1];
                            int nx2=k+dx[k2],ny2=l+dy[k2];
                            checkMax(Trans,Dp[nx1][ny1][nx2][ny2]);
                        }
                    if(i==k&&j==l) Trans-=Mp[i][j];
                    Dp[i][j][k][l]=Trans+Mp[i][j]+Mp[k][l];
                }
    write(Dp[N][N][N][N]);
    return 0;
}
/*
8
2 3 13
2 6  6
3 5  7
4 4 14
5 2 21
5 6  4
6 3 15
7 2 14
0 0  0
*/

加强版

$n$ 的范围扩大 $5$ 倍，选的次数变成了 $k,k<10$ ，反正 $\mathcal O(2^{k}n^{2k})$ 是肯定过不了了，所以考虑另外一种解法：

走完一条路，得到这条路的贡献并把这条路删去，总感觉和什么东西很像。

网络流！！！

那么就考虑用网络流来做这道题，把贡献当作流量肯定不现实，因为即使流量流完了，我们依然可以通过这条道路，只是没有贡献了。

所以考虑费用流，最大费用流。

因为贡献在点上，所以考虑拆点，连接 $(u_{in},u_{out},1,-c)$ ，表示贡献为 $c$ ，但只能取一次，并有 $(u_{in},u_{out},inf,0)$ ，表示可以通过无数次，但没有贡献。

然后点与点之间的话，流量为 $inf$ ，贡献依然为 $0$ 。

然后让 $(1,1)$ 连接源点，$(n,n)$ 连接汇点，容量为 $k$ ，因为只能走 $k$ 次，即可。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
const int MAXV=1e4+10,MAXE=2e5+10,MAXN=1e2+10;
const int INF=0x3f3f3f3f;
int N,K,S,T;
struct Net
{
    int next,to,val,cost;
}Edge[MAXE<<1];
int Head[MAXV],Cur[MAXV],Total=1;
inline void addEdge(int u,int v,int w,int c)
{
    Edge[++Total]=(Net){Head[u],v,w,c};Head[u]=Total;
    Edge[++Total]=(Net){Head[v],u,0,-c};Head[v]=Total;
}
int Dist[MAXV],ret;
bool Vis[MAXV];
inline bool Spfa()
{
    memset(Dist,0x3f,sizeof(Dist));
    memcpy(Cur,Head,sizeof(Head));
    std::queue<int>Q;
    Q.push(S),Dist[S]=0;
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        Vis[u]=0;
        for(int e=Head[u],v;e;e=Edge[e].next)
        {
            v=Edge[e].to;
            if(Dist[v]>Dist[u]+Edge[e].cost&&Edge[e].val)
            {
                Dist[v]=Dist[u]+Edge[e].cost;
                if(!Vis[v]) Vis[v]=1,Q.push(v);
            }
        }
    }
    return Dist[T]!=INF;
}
int Dfs(int x,int inf)
{
    if(x==T) return inf;
    int flow=0;Vis[x]=1;
    for(int e=Cur[x],v;e&&flow<inf;e=Edge[e].next)
    {
        v=Edge[e].to,Cur[x]=e;
        if(!Vis[v]&&Dist[v]==Dist[x]+Edge[e].cost&&Edge[e].val)
        {
            int k=Dfs(v,std::min(Edge[e].val,inf-flow));
            if(k)
            {
                ret+=k*Edge[e].cost;
                Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
            }
        }
    }
    Vis[x]=0;
    return flow;
}
inline int SSP()
{
    int r=0,flow;
    while(Spfa()) while(flow=Dfs(S,INF)) r+=flow;
    return r;
}
int Mp[MAXN][MAXN];
inline int getId(int x,int y,int id)
{
    return (N*(x-1)+y)+id*N*N;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,K);
    S=0,T=N*N*2+1;
    for(int i=1;i<=N;++i)
        for(int j=1;j<=N;++j)
            read(Mp[i][j]);
    addEdge(S,getId(1,1,0),K,0),addEdge(getId(N,N,1),T,K,0);
    for(int i=1;i<=N;++i)
        for(int j=1;j<=N;++j)
            addEdge(getId(i,j,0),getId(i,j,1),1,-Mp[i][j]),addEdge(getId(i,j,0),getId(i,j,1),INF,0);
    for(int i=1;i<=N;++i)
        for(int j=2;j<=N;++j)
            addEdge(getId(i,j-1,1),getId(i,j,0),INF,0);
    for(int i=2;i<=N;++i)
        for(int j=1;j<=N;++j)
            addEdge(getId(i-1,j,1),getId(i,j,0),INF,0);
    SSP();
    write(-ret);
    return 0;
}
/*
3 1
1 2 3
0 2 1
1 4 2
*/
相关文章