C++11(clang++ 3.9) 解法, 执行用时: 22ms, 内存消耗: 464K, 提交时间: 2020-03-17 14:49:13

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int INF=100000000;
const int MAXN=1010;
const int MAXM=1010000;
#define ll int
struct Edge
{
	int u,v;
	ll cost;
}edge[MAXM];
int pre[MAXN],id[MAXN],visit[MAXN],edgenum;
void addedge(int u,int v,int cost)
{
	Edge E={u,v,cost};
	edge[edgenum++]=E;
}
ll in[MAXN];
ll zhuliu(int root,int n,int m,Edge edge[],int c)
{
	int u,v;
	ll res=0;
	while(1)
	{
		for(int i=0;i<n;i++)
		in[i]=INF;
		for(int i=0;i<m;i++)
		if(edge[i].u!=edge[i].v&&edge[i].cost<in[edge[i].v])
		{
			pre[edge[i].v]=edge[i].u;
			in[edge[i].v]=edge[i].cost;
		}
		for(int i=0;i<n;i++)
		if(i!=root&&in[i]==INF)
		return -1;
		int tn=0;
		memset(id,-1,sizeof(id));
		memset(visit,-1,sizeof(visit));
		in[root]=0;
		for(int i=0;i<n;i++)
		{
			res+=in[i];
			if(res>c) return -1;
			v=i;
			while(visit[v]!=i&&id[v]==-1&&v!=root)
			{
				visit[v]=i;
				v=pre[v];
			}
			if(v!=root&&id[v]==-1)
			{
				for(int u=pre[v];u!=v;u=pre[u])
				id[u]=tn;
				id[v]=tn++;
			}
		}
		if(tn==0) break;
		for(int i=0;i<n;i++)
		if(id[i]==-1)
		id[i]=tn++;
		for(int i=0;i<m;)
		{
			v=edge[i].v;
			edge[i].u=id[edge[i].u];
			edge[i].v=id[edge[i].v];
			if(edge[i].u!=edge[i].v)
			edge[i++].cost-=in[v];
			else
			swap(edge[i],edge[--m]);
		}
		n=tn;
		root=id[root];
	 } 
	 return res;
}
void init()
{
	edgenum=0;
}
struct node
{
	ll u,v,bit,cost;
}E[MAXM];
int n,m,c;
bool ok(int x)
{
	init();
	for(int i=0;i<m;i++)
	if(E[i].bit>=x)
	addedge(E[i].u,E[i].v,E[i].cost);
	int ans=zhuliu(0,n,edgenum,edge,c);
	return ans<=c&&ans!=-1;
}
int main()
{
	int T,i;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d %d %d",&n,&m,&c);
		for(i=0;i<m;i++)
		scanf("%d %d %d %d",&E[i].u,&E[i].v,&E[i].bit,&E[i].cost);
		int l=1,r=1000000;
		int ans=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(ok(mid))
			l=mid+1,ans=max(ans,mid);
			else r=mid-1;
		}
		ans==0?puts("NO"):printf("%d\n",ans);
	}
	return 0;
}