【题解】星际转移问题网络流24题

Prelude

传送到洛谷：→_→
传送到LOJ：←_←
这道题看着觉得特别复杂，不太会做，加上刚学网络流，对这些题没有什么思路。就这样，看了看WC2017讲义上的题解，大概知道思路了，后来还是不太会，又看了看别人的代码。。。

Solution

这题的解法是这样的。首先对于所有太空船能到达的太空站做一个并查集，来判断问题是否有解（网上也有很多当天数达到一定的时候就判断问题无解的，不太清楚怎么证明最大天数，而且这样个人认为比较慢吧。。。）。
建图是这样建的：把地球和太空站拆成每一天是一个点，月球是汇点。从源点向每一天的地球连一条容量为INF的边。然后把通过太空船从上一天在的太空站到这一天的当前的太空站也连一条容量为\(h[i]\)的边。由于人可以在地球、太空站上过若干天，所以把上一天的地球、太空站和这一天的它自己也连一条容量为INF的边。一天接着一天地连边，连完之后跑Dinic，看下最大流能增加多少，如果最大流的总量超过了\(k\)，那么就说明到这一天人可以全部送往月球，就输出当前天数，终止程序。
（Ps：我一开始数组\(h\)和\(r\)开小了，没看到\(m\leq 20\)，结果交上去\(m=20\)的点\(k\)的值从50变成了4，以后一定要看清楚数据范围，数组注意多开一点防止越界）
2018年的第一发提交就是这题了，90分，从去年做到今年。。。我其实交之前下了数据测的（逃），还改了改代码，然而Windows并不会越界，就没查出最后一个点的问题来。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 1000010;
const int INF = 1e9;
struct Edge {
    int from,to,cap,flow;
    Edge () {}
    Edge (int from,int to,int cap,int flow): from(from),to(to),cap(cap),flow(flow) {}
};
struct Dinic {
    int n,m,s,t;
    vector <int> g[MAXN];
    vector <Edge> edges;
    bool vis[MAXN];
    int d[MAXN];
    int cur[MAXN];
    void addedge(int from,int to,int cap)
    {
        edges.push_back(Edge(from,to,cap,0));
        edges.push_back(Edge(to,from,0,0));
        m = edges.size();
        g[from].push_back(m-2);
        g[to].push_back(m-1);
    }
    bool bfs()
    {
        memset(vis,0,sizeof vis);
        queue <int> q;
        vis[s] = 1;
        d[s] = 0;
        q.push(s);
        while(!q.empty())
        {
            int now = q.front();
            q.pop();
            for(int i = 0; i < g[now].size(); ++i)
            {
                Edge &e = edges[g[now][i]];
                if(!vis[e.to] && e.cap > e.flow)
                {
                    vis[e.to] = 1;
                    d[e.to] = d[now] + 1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int dfs(int x,int res)
    {
        if(x == t || !res) return res;
        int flow = 0,f = 0;
        for(int &i = cur[x]; i < g[x].size(); ++i)
        {
            Edge &e = edges[g[x][i]];
            if(d[x] + 1 == d[e.to] && (f = dfs(e.to,min(res,e.cap - e.flow))) > 0)
            {
                e.flow += f;
                edges[g[x][i]^1].flow -= f;
                flow += f;
                res -= f;
                if(!res) break;
            }
        }
        return flow;
    }
    int maxflow(int s,int t)
    {
        this->s = s;
        this->t = t;
        int flow = 0;
        while(bfs())
        {
            memset(cur,0,sizeof cur);
            flow += dfs(s,INF);
        }
        return flow;
    }
}dinic;
int n,m,k;
int h[21],r[21];
int a[20][20];
int fa[20];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]);}
void uni(int x,int y) { int fx = find(x),fy = find(y); if(fx != fy) fa[fx] = fy;}
int num(int _day,int space) { if(space == n+2) return 1000000; return (n+1)*(_day)+space;}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1; i <= n+2; ++i) fa[i] = i;
    int nowa;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d",h+i,r+i);
        for(int j = 1; j <= r[i]; ++j)
        {
            scanf("%d",&nowa);
            if(nowa == 0) a[i][j] = n + 1;
            else
            {
                if(nowa == -1) a[i][j] = n + 2;
                else a[i][j] = nowa;
            }
            if(j > 1) uni(a[i][j-1],a[i][j]);
        }
    }
    if(find(n+1) != find(n+2))
    {
        puts("0");
        return 0;
    }
    int di = n + 1;
    int yue = 1000000;
    int day = 1;
    int nowflow = 0;
    dinic.addedge(0,num(0,di),INF);
    for(;; ++day)
    {
        dinic.addedge(0,num(day,di),INF);
        for(int i = 1; i <= m; ++i)
        {
            int lastday = ((day-1)+1) % r[i];
            int nowday = (day+1) % r[i];
            if(!lastday) lastday = r[i];
            if(!nowday) nowday = r[i];
            dinic.addedge(num(day-1,a[i][lastday]),num(day,a[i][nowday]),h[i]);
        }
        for(int i = 1; i <= n + 1; ++i)
            dinic.addedge(num(day-1,i),num(day,i),INF);
        nowflow += dinic.maxflow(0,yue);
        if(nowflow >= k) {printf("%d\n",day); return 0;}
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

const int MAXN = 1000010;

const int INF = 1e9;

struct Edge {

int from,to,cap,flow;

Edge () {}

Edge (int from,int to,int cap,int flow): from(from),to(to),cap(cap),flow(flow) {}

};

struct Dinic {

int n,m,s,t;

vector <int> g[MAXN];

vector <Edge> edges;

bool vis[MAXN];

int d[MAXN];

int cur[MAXN];

void addedge(int from,int to,int cap)

{

edges.push_back(Edge(from,to,cap,0));

edges.push_back(Edge(to,from,0,0));

m = edges.size();

g[from].push_back(m-2);

g[to].push_back(m-1);

}

bool bfs()

{

memset(vis,0,sizeof vis);

queue <int> q;

vis[s] = 1;

d[s] = 0;

q.push(s);

while(!q.empty())

{

int now = q.front();

q.pop();

for(int i = 0; i < g[now].size(); ++i)

{

Edge &e = edges[g[now][i]];

if(!vis[e.to] && e.cap > e.flow)

{

vis[e.to] = 1;

d[e.to] = d[now] + 1;

q.push(e.to);

}

return vis[t];

}

int dfs(int x,int res)

{

if(x == t || !res) return res;

int flow = 0,f = 0;

for(int &i = cur[x]; i < g[x].size(); ++i)

{

Edge &e = edges[g[x][i]];

if(d[x] + 1 == d[e.to] && (f = dfs(e.to,min(res,e.cap - e.flow))) > 0)

{

e.flow += f;

edges[g[x][i]^1].flow -= f;

flow += f;

res -= f;

if(!res) break;

}

return flow;

}

int maxflow(int s,int t)

{

this->s = s;

this->t = t;

int flow = 0;

while(bfs())

{

memset(cur,0,sizeof cur);

flow += dfs(s,INF);

}

return flow;

}

}dinic;

int n,m,k;

int h[21],r[21];

int a[20][20];

int fa[20];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]);}

void uni(int x,int y) { int fx = find(x),fy = find(y); if(fx != fy) fa[fx] = fy;}

int num(int _day,int space) { if(space == n+2) return 1000000; return (n+1)*(_day)+space;}

int main()

{

scanf("%d%d%d",&n,&m,&k);

for(int i = 1; i <= n+2; ++i) fa[i] = i;

int nowa;

for(int i = 1; i <= m; ++i)

{

scanf("%d%d",h+i,r+i);

for(int j = 1; j <= r[i]; ++j)

{

scanf("%d",&nowa);

if(nowa == 0) a[i][j] = n + 1;

else

{

if(nowa == -1) a[i][j] = n + 2;

else a[i][j] = nowa;

}

if(j > 1) uni(a[i][j-1],a[i][j]);

}

if(find(n+1) != find(n+2))

{

puts("0");

return 0;

}

int di = n + 1;

int yue = 1000000;

int day = 1;

int nowflow = 0;

dinic.addedge(0,num(0,di),INF);

for(;; ++day)

{

dinic.addedge(0,num(day,di),INF);

for(int i = 1; i <= m; ++i)

{

int lastday = ((day-1)+1) % r[i];

int nowday = (day+1) % r[i];

if(!lastday) lastday = r[i];

if(!nowday) nowday = r[i];

dinic.addedge(num(day-1,a[i][lastday]),num(day,a[i][nowday]),h[i]);

}

for(int i = 1; i <= n + 1; ++i)

dinic.addedge(num(day-1,i),num(day,i),INF);

nowflow += dinic.maxflow(0,yue);

if(nowflow >= k) {printf("%d\n",day); return 0;}

}

return 0;

}