大兴区企业网站建设,酒店品牌策划方案,福州网站建设报价,网站 建设 流行 数据库手抄代码 学习指针 冥思苦想一晚上终于——在一瞬间开窍了。果然题目都是这样#xff1a;突破了一个点#xff0c;一切都是柳暗花明。 题面描述#xff1a; 样例#xff1a; 这道题目#xff0c;首先注意到给定的边的性质#xff1a;这些边在平面上构成了一棵树#x… 手抄代码 学习指针 冥思苦想一晚上终于——在一瞬间开窍了。果然题目都是这样突破了一个点一切都是柳暗花明。 题面描述 样例 这道题目首先注意到给定的边的性质这些边在平面上构成了一棵树区间之间互不相交只有包含与外离两种关系。如果不考虑颜色的限制我们将原图的边权转化为网络流中的流量那么原图中的最短路就转化为了新图中的最小割。那么在张网络流的图上我们应当如何限制颜色的制约关系呢 首先一个明显的思路这张图是一个树形的结构画在一个类似数轴的东西上面会很容易发现最下面的一条链上的点是无论如何都要经过的而不存在于这条链上的点则一定不会被访问到其所代表的颜色也一定不会被我们所选择。对于这样的点我们将它们从我们的图上删去。最小割将图中的点分做S割与T割的两个部分。我们对于每一个颜色都做出一个辅助点若这个点位于S割代表这个颜色被选择位于T割代表不被选择。 我们将所有的边画成树后从所有的大区间层层推进的向其所包含的小区间连边类似线段树。注意在这里我们先忽略那些链接相邻两点的区间不作处理。一个显然的性质一个大区间所跳过的点一定包含了所有它包含的小区间跳过的点。那么我们就从区间往它跳过的颜色的点连上INF的边如果大区间小区间共同跳过了一个颜色这条边从小区间-颜色。注意之前我们确定一定不会经过的颜色从它向T点连INF的边保证它一定处于T割。 这样我们可以发现如果不选择这一个点说明我们的割线一定在这个颜色的点的上方-我们选择了所有跳过这个颜色的区间。如果选择一个点说明我们的割线在这个点的下方-我们没有选择任何一个跳过这个颜色的区间。这样限制就得以满足了。最后那些链接相邻两点的边如果包含于大区间则由这些区间其中最小的一个向T点连边权值的流量的边否则就从S连向T流量也为边权值。 感觉读懂了之后除了感叹还是感叹——我学过网络流吗不存在的。【摊手】 #include bits/stdc.h
using namespace std;
#define maxn 10000
#define INF 99999
#define pb push_back
#define vec vector
int n, m, cnp, cnt, s, t;
int Map[maxn][maxn], lev[maxn], nxt[maxn];
int ans, a[maxn], id[maxn];
bool tag[maxn], mark[maxn], flag[maxn];
vector int u, v, w, c;
queue int q;int read()
{int x 0, k 1;char c;c getchar();while(c 0 || c 9) { if(c -) k -1; c getchar(); }while(c 0 c 9) x x * 10 c - 0, c getchar();return x * k;
} struct node
{int u, v, w; bool flag;bool operator (node t){ return v - u t.v - t.u; } // 区间长度短的放在前面
}E[maxn]; struct edge
{int v, f;edge *nxt, *rev;
}e[100000], *p e, *head[maxn], *cur[maxn];void add(int u, int v, int f1, int f2)
{*p (edge) { v, f1, head[u], p 1 }, head[u] p ;*p (edge) { u, f2, head[v], p - 1 }, head[v] p ;
}bool bfs()
{memset(lev, 0, sizeof(lev));q.push(s); lev[s] 1;while(!q.empty()){int u q.front(); q.pop();for(edge *i head[u]; i; i i - nxt){if(!lev[i - v] i - f) {lev[i - v] lev[u] 1;q.push(i - v); }}}return lev[t];
}int dfs(int x, int nf)
{int ff 0;if(x t) return nf;for(edge *i cur[x]; i; i i - nxt){if(!nf) break;if(i - f lev[i - v] lev[x] 1){int af dfs(i - v, min(nf, i - f));i - f - af, i - rev - f af, cur[x] i;ff af, nf - af;}}cur[x] head[x]; return ff;
}int Work(vec int u, vec int v, vec int w, vec int c)
{memset(Map, 80, sizeof(Map));for(int i 0; i (int) u.size(); i ) Map[u[i]][v[i]] Map[v[i]][u[i]] min(Map[u[i]][v[i]], w[i]);flag[n] 1;for(int i n - 1; i; i --)for(int j i 1; j n; j )flag[i] | flag[j] Map[i][j] 1 30;for(int i 0; i n; i nxt[i]){a[id[i] cnt] i; nxt[i] n 1;for(int j i 1; j n; j )if(Map[i][j] 1 30 nxt[i] n flag[j]){ nxt[i] j; break; }for(int j 0; j i; j )if(Map[i][j] 1 30 id[j] id[j] ! cnt - 1)E[ cnp] (node) { id[j], cnt, Map[i][j], 0 };} if(a[cnt] ! n) return -1;E[ cnp] (node) { id[0], id[n], 0, 0 }; sort(E 1, E cnp);s cnp, t cnp 1001; for(int i 1; i n - 1; i )if(!id[i]) add(cnp c[i - 1], t, 1 30, 1 30); for(int i 1; i cnp; i ){for(int j 1; j i; j )if(!E[j].flag E[i].u E[j].u E[i].v E[j].v)E[j].flag 1, add(i, j, E[j].w, 1 30);for(int j E[i].u 1; j E[i].v; j )if(!tag[j]) tag[j] 1, add(i, cnp c[a[j] - 1], 1 30, 1 30);for(int j E[i].u; j E[i].v; j )if(!mark[j]) mark[j] 1, add(i, t, Map[a[j]][a[j 1]], 0);} for(int i 1; i t; i ) cur[i] head[i];while(bfs()) if((ans dfs(s, 1 30)) INF) return -1;return ans;
}int main()
{n read(), m read();for(int i 1; i n - 1; i ){int x read();c.pb(x);}for(int i 1; i m; i ){int x read(), y read(), z read();u.pb(x), v.pb(y), w.pb(z);}printf(%d\n, Work(u, v, w, c));return 0;
} 转载于:https://www.cnblogs.com/twilight-sx/p/8763263.html
