AcrosstheFirewall

First line contains two integers n and $m ~ (2 \leq n \leq 200, 1 \leq m \leq 1000)$ .

The second line contains n integers $a_1, a_2, a_3, \cdots, a_n ~ (1 \leq a_1 \leq 209\,715\,200, 1 \leq a_2, a_3, \cdots, a_n \leq 1\,048\,576)$ for the computers.

Next m lines each contains three integers $u_i, v_i, w_i ~ (1 \leq u_i, v_i \leq n, 1 \leq w_i \leq 1048576)$ for the rules.

The last line of input contains two integers k and $s ~ (2 \leq k \leq n, 1 \leq s \leq 10^{9})$ .

Output a number for the answer with an absolute or relative error of at most $10^{-4}$ . Precisely speaking, assume that your answer is a and and the jury's answer is b, your answer will be considered correct if $\frac{|a-b|}{max\lbrace 1, |b|\rbrace} \leq 10^{-4}$ , where $\max\lbrace x,y\rbrace$ means the maximum of x and y and |x| means the absolute value of x.

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 632K, 提交时间: 2020-06-13 17:12:34

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
const int mod=1000000007;
char s[N];
ll a[N];
ll ans[N];
ll b[N];
ll net[N][N];
ll use[N][N];
vector<pair<ll,ll>>v[N];
bool vis[256];
ll mn,flag;
void dfs(int x) {
    vis[x]=1;
    if(x==1) {
        flag=1;
        return ;
    }
    for(auto &i:v[x]) {
        if(vis[i.first]) continue;
        if(a[i.first]-b[i.first]==0||i.second-use[i.first][x]==0) continue;
        ll tmp=mn;
        mn=min(min(mn,i.second-use[i.first][x]),a[i.first]-b[i.first]);
        dfs(i.first);
        if(flag) {
            b[i.first]+=mn;
            use[i.first][x]+=mn;
            use[x][i.first]+=mn;
            break;
        }
        mn=tmp;
    }
}
int main(){
    ios::sync_with_stdio(false), cin.tie(0);
    int n,m,t,k,s;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++) {
        int x,y,w;
        cin>>x>>y>>w;
        v[x].push_back({y,w});
        v[y].push_back({x,w});
    }
    cin>>k>>s;
    flag=1;
    while(flag) {
        flag=0;
        memset(vis,0,sizeof vis);
        mn=a[k]-b[k];
        if(mn==0) break;
        dfs(k);
        b[k]+=mn;
    }
    printf("%.10f\n",s*1.0/b[k]);
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 492K, 提交时间: 2020-06-15 23:21:27

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
int n,m,s,ans,dep[405],que[405];
struct edge{
	int w,to,rev;
};
vector<edge> e[405];
bool bfs(){
	int i,x,sz,head=0,tail=1;
	memset(dep,0,sizeof(dep));
	dep[1]=que[1]=1;
	while (head^tail){
		x=que[++head];
		for (i=0,sz=e[x].size();i<sz;i++)
		if (!dep[e[x][i].to]&&e[x][i].w){
			dep[e[x][i].to]=dep[x]+1;
			que[++tail]=e[x][i].to;
		}
	}
	return dep[n+m];
}
int dfs(int x,int flow){
	int i,z,sz,res=0;
	if (!flow||x==n+m) return flow;
	for (i=0,sz=e[x].size();i<sz;i++)
	if (dep[e[x][i].to]>dep[x]&&e[x][i].w){
		z=dfs(e[x][i].to,min(flow,e[x][i].w));
		e[x][i].w-=z;
		e[e[x][i].to][e[x][i].rev].w+=z;
		flow-=z;
		res+=z;
		if (!flow) return res;
	}
	dep[x]=0;
	return res;
}
void dinic(){
	ans=0;
	while (bfs()) ans+=dfs(1,INF);
}
int main(){
	int i,x,y,z;
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++){
		scanf("%d",&x);
		e[i].push_back((edge){x,n+i,e[n+i].size()});
		e[n+i].push_back((edge){0,i,e[i].size()-1});
	}
	while (m--){
		scanf("%d%d%d",&x,&y,&z);
		e[x].push_back((edge){z,y,e[y].size()});
		e[y].push_back((edge){0,x,e[x].size()-1});
	}
	scanf("%d%d",&m,&s);
	dinic();
	printf("%.8f",1.0*s/ans);
	return 0;
}

详情