loj2308 「APIO2017」商旅

ref
#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

using namespace std;

typedef long long ll;

int n, m, k, uu, vv, hea[105], cnt, tot[105];

ll b[105][1005], s[105][1005], w[105][105], bst[105][105], dis[105], ww;

bool ins[105];

const ll oo=0x3f3f3f3f3f3f3f3f;

queue<int> d;

struct Edge{

	int too, nxt;

	ll val;

}edge[20005];

void add_edge(int fro, int too, ll val){

	edge[++cnt].nxt = hea[fro];

	edge[cnt].too = too;

	edge[cnt].val = val;

	hea[fro] = cnt;

}

bool chk(ll lim){

	memset(hea, 0, sizeof(hea));

	memset(dis, 0, sizeof(dis));

	while(!d.empty())	d.pop();

	cnt = 0;

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

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

			if(bst[i][j]!=-1 && w[i][j]<oo)

				add_edge(i, j, bst[i][j]-lim*w[i][j]);

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

		d.push(i);

		tot[i] = ins[i] = 1;

	}

	while(!d.empty()){

		int x=d.front();

		d.pop();

		ins[x] = false;

		for(int i=hea[x]; i; i=edge[i].nxt){

			int t=edge[i].too;

			if(dis[t]<=dis[x]+edge[i].val){//这里是大于等于，零环也合法

				tot[t] = tot[x] + 1;

				if(tot[t]>n)	return true;

				dis[t] = dis[x] + edge[i].val;

				if(!ins[t]){

					ins[t] = true;

					d.push(t);

				}

			}

		}

	}

	return false;

}

int main(){

	memset(w, 0x3f, sizeof(w));

	memset(bst, -1, sizeof(bst));

	cin>>n>>m>>k;

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

		for(int j=1; j<=k; j++)

			scanf("%lld %lld", &b[i][j], &s[i][j]);

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

		w[i][i] = 0;

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

		scanf("%d %d %lld", &uu, &vv, &ww);

		w[uu][vv] = min(w[uu][vv], ww);

	}

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

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

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

				w[i][j] = min(w[i][j], w[i][l]+w[l][j]); 

	ll l=0, r=0, mid, re;

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

		for(int j=1; j<=n; j++){

			if(i!=j && w[i][j]<oo){

				bst[i][j] = 0;

				for(int l=1; l<=k; l++)

					if(s[j][l]!=-1 && b[i][l]!=-1)

						bst[i][j] = max(bst[i][j], s[j][l]-b[i][l]);

				r = max(r, bst[i][j]);

			}

		}

	while(l<=r){

		mid = (l + r) >> 1;

		if(chk(mid))	re = mid, l = mid + 1;

		else	r = mid - 1;

	}

	cout<<re<<endl;

	return 0;

}
巴特西

loj2308 「APIO2017」商旅

最新文章

热门文章
