这个题要求最大边最小，很明显要二分答案。

考虑验证谓词[tex]C(x)[/tex]。我们可以将所有边权小于等于[tex]x[/tex]的边加入图，然后判断是否有[tex]T[/tex]条从1到N的不重复路径。

不过这个怎么做呢？我们可以把边加入（注意我们要加入的边都是无向边），并把容量设为1，从1到N跑一遍最大流，就是不重复路径条数。

为什么可以这样呢？每个边容量只有1，最多只能让一条路径使用并“推送”到终点，所以从1到N的最大流就是不重复路径条数辣。

代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=205,maxp=40005;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))

namespace Dinic{
	struct Edge{
		int u,v,cap,flow;
	};
    vector<Edge> edges;
    vector<int> G[maxn];
    int m;
    inline void AddEdge(int u,int v,int cap){
        edges.push_back((Edge){u,v,cap,0});
        edges.push_back((Edge){v,u,0,0});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
	inline void ClearGraph(){
		register int i;
		edges.clear();
		m=0;
		REP(i,maxn){
			G[i].clear();
		}
	}
    bool vis[maxn];
    int d[maxn],cur[maxn];
    int s,t;
    inline bool BFS(){
        register int i,u;
        queue<int> Q;
        CL_ARR(vis,0);
        Q.push(s);
        d[s]=0;
        vis[s]=true;
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            REP(i,G[u].size()){
                Edge& e=edges[G[u][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    vis[e.v]=1;
                    d[e.v]=d[u]+1;
                    Q.push(e.v);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x,int a){
        if(x==t || a==0)
            return a;
        int flow=0,temp;
        for(int& i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if(d[e.v]==d[x]+1){
                temp=DFS(e.v,min(a,e.cap-e.flow));
                if(temp>0){
                    e.flow+=temp;
                    edges[G[x][i]^1].flow-=temp;
                    flow+=temp;
                    a-=temp;
                    if(a==0)
                        break;
                }
            }
        }
        return flow;
    }
    inline int Maxflow(int S,int T){
        s=S;
        t=T;
        register int ans=0;
        while(BFS()){
            CL_ARR(cur,0);
            ans+=DFS(s,0x7f7f7f7f);
        }
        return ans;
    }
};

struct Edge{
	int u,v,d;
	bool operator <(const Edge& x) const{
		return d<x.d;
	}
};
Edge EdgePool[maxp];
int n,p,t;
inline bool Check(int x){
	register int i;
	Dinic::ClearGraph();
	REP_B(i,p){
		if(EdgePool[i].d>x)
			break;
		Dinic::AddEdge(EdgePool[i].u,EdgePool[i].v,1);
		Dinic::AddEdge(EdgePool[i].v,EdgePool[i].u,1);
	}
	if((Dinic::Maxflow(1,n))<t)
		return false;
	else
		return true;
}
int main(){
	register int i,L=0,M,R=0;
	scanf("%d%d%d",&n,&p,&t);
	REP_B(i,p){
		scanf("%d%d%d",&EdgePool[i].u,&EdgePool[i].v,&EdgePool[i].d);
		R=max(R,EdgePool[i].d+1);
	}
	sort(EdgePool+1,EdgePool+1+p);
	while(L<R){
		M=L+(R-L)/2;
		if(Check(M))
			R=M;
		else
			L=M+1;
	}
	printf("%d\n",L);
	return 0;
}

• 相关文章
• 全局相关文章