[网络流24题]星际转移问题

C++(g++ 7.5.0) 解法, 执行用时: 6ms, 内存消耗: 3624K, 提交时间: 2022-12-28 13:21:19

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 500010, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], f[M], idx, d[N], n, m, k, S, T, cur[M], H[N], p[N];
vector<int>num[N];
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
    e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx ++; 
}

int find(int x)
{
	if(p[x] != x) return p[x] = find(p[x]);
	return p[x];
}
bool bfs()
{
    queue<int>q;
    memset(d, -1, sizeof d);
    q.push(S);
    d[S] = 0;
    cur[S] = h[S];
    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if((d[j] == -1) && f[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if(j == T) return true;
                q.push(j);
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        int j = e[i];
        cur[u] = i;
        if((d[j] == d[u] + 1) && f[i])
        {
            int t = find(j, min(f[i], limit - flow));
            if(!t) d[j] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0, flow;
    while(bfs()) while(flow = find(S, 0x3f3f3f3f)) r += flow;
    	
    return r;
}
int get(int day, int id)
{
	return day * (n + 2) + id;
}
int main()
{
	cin >> n >> m >> k;
	memset(h, -1, sizeof h);

	for(int i = 0; i <= n + 1; i ++ ) p[i] = i;
	for(int i = 1; i <= m; i ++ )
	{
		cin >> H[i];
		int x;
		cin >> x;
		int id;
		while(x -- ) 	
		{
			cin >> id;
			if(id == -1) id = n + 1;
			num[i].push_back(id);
		}

		for(int j = 1; j < num[i].size(); j ++ )
		{
			int a = num[i][j - 1], b = num[i][j];
			a = find(a), b = find(b);
			p[a] = b;
		}
	}

	if(find(0) != find(n + 1)) 
	{
		cout << 0 << '\n';
		return 0;
	}

	S = N - 2, T = N - 1;

	add(S, get(0, 0), k);
	add(get(0, n + 1), T, INF);
	int sum = 0;


	for(int i = 1; ; i ++ )
	{
	    add(get(i, n + 1), T, INF);
		for(int j = 0; j <= n; j ++ ) add(get(i - 1, j), get(i, j), INF);

		for(int j = 1; j <= m; j ++ )
		{
		    int a = num[j][(i - 1) % (int)num[j].size()], b = num[j][i % (int)num[j].size()];
		    add(get(i - 1, a), get(i, b), H[j]);
		}
		sum += dinic();
		if(sum >= k) 
		{
			cout << i << '\n';
			return 0;
		}
	}
}

C++(clang++ 11.0.1) 解法, 执行用时: 64ms, 内存消耗: 728K, 提交时间: 2022-10-04 22:05:18

#include <bits/stdc++.h>
#define inf 100
#define N 10010
using namespace std;
int n,m,k,P[21],s=1,t=0;
vector<int> e[21];
int l,r,mid;
struct edg{
	int t,next,w;
}edge[10*N];
int d[N],q[N]; // d[i]是层数，q是手工栈 
int head[N],hcnt=-1;
int ans;
void addedge(int x,int y,int w){
	edge[++hcnt].t=y;
	edge[hcnt].w=w;
	edge[hcnt].next=head[x];
	head[x]=hcnt;
}
bool makelevel(int s,int t){
	memset(d,0,sizeof(d));
	memset(q,0,sizeof(q));
	d[s]=1;
	int tl=0,tr=0;
	q[tr++]=s;
	while(tl<tr){
		int x=q[tl++];
		if(x==t) return true;
		for(int i=head[x];i!=-1;i=edge[i].next){
			if(d[edge[i].t]==0 && edge[i].w!=0){
				q[tr++]=edge[i].t;
				d[edge[i].t]=d[x]+1;
			}
		}
	} 
	return false;
}
int dfs(int x,int flow,int t){
	if(x==t) return flow;
	int sum=0;
	for(int i=head[x];i!=-1;i=edge[i].next){
		if(edge[i].w!=0 && d[edge[i].t]==d[x]+1){
			int tmp=dfs(edge[i].t,min(edge[i].w,flow-sum),t);
			edge[i].w-=tmp;
			edge[i^1].w+=tmp;
			sum+=tmp;
			if(sum==flow) return sum;
		}
	}
	return sum;
}
signed main(){
	memset(head,-1,sizeof(head));
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++){
		scanf("%d",&P[i]);
		scanf("%d",&r);
		for(int j=1;j<=r;j++){
			scanf("%d",&l);
			e[i].push_back(l+1);
		}
	}
	int day=0;
    while(day<500){
        for(int i=1;i<=(n+1);i++){
            addedge(day*(n+1)+i,(day+1)*(n+1)+i,inf);
			addedge((day+1)*(n+1)+i,day*(n+1)+i,0);
        }
        for(int i=1;i<=m;i++){
            int siz=e[i].size();
			int from=day*(n+1)+e[i][day%siz];
			int to=(day+1)*(n+1)+e[i][(day+1)%siz];
			if(e[i][day%siz]==t ) from=t;
			if(e[i][(day+1)%siz]==t ) to=t;
			addedge(from,to,P[i]);
			addedge(to,from,0);
        }
        while(makelevel(s,t)){
            ans+=dfs(s,inf,t);
        }
        day++;
        if(ans>=k) break;
        
    }
	if(day==500)printf("0");
    else printf("%d\n",day);
	return 0;
}

详情