[JSOI2008]BLUE MARY的旅行

C++(g++ 7.5.0) 解法, 执行用时: 10ms, 内存消耗: 700K, 提交时间: 2022-09-25 10:54:22

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010, M = 200010, INF = 0x3f3f3f3f;

int n, m, t, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
int g[51][51];

void insert(int u, int v, int d) {
    e[idx] = v, ne[idx] = h[u], f[idx] = d, h[u] = idx++;
    e[idx] = u, ne[idx] = h[v], f[idx] = 0, h[v] = idx++;
}

bool bfs() {
    int hh = 0, tt = -1;
    memset(d, -1, sizeof d);
    q[++tt] = S;
    d[S] = 0;
    cur[S] = h[S];
    while (hh <= tt) {
        int t = q[hh++];
        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[++tt] = 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]) {
        cur[u] = i;
        int j = e[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, INF)) r += flow;
    return r;
}

int get(int x, int day) {
    return (day - 1) * n + x;
}

int main() {
    cin >> n >> m >> t;
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = z;
    }
    S = N - 1, T = S - 1;
    memset(h, -1, sizeof h);
    insert(S, get(1, 1), t);
    int res = 0;
    insert(get(n, 1), T, t);
    for (int day = 2; ; day++) {
        for (int i = 1; i <= n; i++) {
            insert(get(i, day - 1), get(i, day), t);
            for (int j = 1; j <= n; j++) {
                if (!g[i][j]) continue;
                insert(get(i, day - 1), get(j, day), g[i][j]);
            }
        }
        insert(get(n, day), T, t);
        res += dinic();
        if (res == t) {
            cout << day - 1;
            return 0;
        }
    }
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 10ms, 内存消耗: 968K, 提交时间: 2023-05-01 20:36:53

#include <bits/stdc++.h>
#define N 20100
#define M 245010
#define inf 0x7f7f7f7f
using namespace std;
/*
理论复杂度 N^2*M 增加了弧优化
*/
struct edg{
	int t,next,w;
}edge[10*M];
int n,m,s,t,T,ans,x,y,z,e[N][3];
int d[N],q[N]; // d[i]是层数，q是手工栈 
int head[N],cur[N],hcnt=-1;
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));
	memcpy(cur,head,sizeof(head));
	d[s]=1;
	int l=0,r=0;
	q[r++]=s;
	while(l<r){
		int x=q[l++];
		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[r++]=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=cur[x];i!=-1;i=edge[i].next){
		cur[x]=i; // 网络流弧优化 
		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;
}
int main(){
	memset(head,-1,sizeof(head));
	scanf("%d%d%d",&n,&m,&T);
	s=1;t=0;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]);
	}
	int tmp=0,ans;
	for(ans=1;;ans++){
		for(int i=1;i<=n;i++){
			addedge(i+(ans-1)*n,i+ans*n,inf);
			addedge(i+ans*n,i+(ans-1)*n,0);
		}
		for(int i=1;i<=m;i++){
			addedge(e[i][0]+(ans-1)*n,e[i][1]+ans*n,e[i][2]);
			addedge(e[i][1]+ans*n,e[i][0]+(ans-1)*n,0);
		}
		addedge(n+ans*n,t,inf);
		addedge(t,n+ans*n,0);
		while(makelevel(s,t)){
			tmp+=dfs(s,inf,t);
		}	
		//printf("%d %d\n",ans,tmp);
		if(tmp>=T) break;
	}
	printf("%d\n",ans);
	return 0;
}

详情