精华内容
下载资源
问答
  • 那么我们跑一次网络流,如果所有带下界的边满流,那么就存在一种方案了,否则就不存在。 。。。。我的代码能过UVA的,ZOJ的好像过不了。。。不知道哪里还有什么BUG 代码: #include #include #...

    Kim works in a traveling agency in Korea. Recently, his foreign customer gave him an international call and asked him to make a travel plan in Korea. The customer wants to visit two famous roads along which beautiful flowers are in full blossom. The customer would like to fly to a city in the plan and rent a car, enjoy his travel, and return to the city where he started. He does not want to visit the same city or the same road twice. Also, he hates to travel along any toll roads. It does not matter how many cities are included in the plan. Can Kim make a travel plan satisfying the requirements? For example, see the maps in Figure 1. In the figure a circle represents a city and the line between two cities represents the road between them. The two bold lines represent the famous roads that the customer wants to visit and the dotted line is a toll road.

    \epsfbox{p3604.eps} Figure 1
    In case of Figure 1(a), Kim can make travel plans such as 1 $ \rightarrow$ 2 $ \rightarrow$ 4 $ \rightarrow$ 5 $ \rightarrow$ 3 $ \rightarrow$ 1 and 2 $ \rightarrow$ 3 $ \rightarrow$ 5 $ \rightarrow$ 4 $ \rightarrow$ 2 . In case of Figure 1(b), Kim can not make any plan satisfying the requirements. You are to write a program to help Kim. For a given map with two famous roads and some toll roads, your program should determine whether there can be a travel plan satisfying the requirements.

    Input 

    Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing two integers N and M , the number of cities and the number of roads in the map, respectively, where 5$ \le$N$ \le$1000 . In the next M lines, each line contains two positive integers that represent a road connecting two cities. In the next two lines, each line contains a road that the customer wants to visit. In the next line, the number of toll roads F is given, 0$ \le$F$ \le$M . In the next F lines, each line contains toll roads. Assume the cities are labeled from 1 to N and there is at most one road between two cities. Also, assume the two roads that the customer wants to visit are not toll roads.

    Output 

    Your program is to write to standard output. Print exactly one line for each test case. For each test case, print YES if there can be a travel plan satisfying the requirements. Otherwise, print NO. The following shows sample input and output for three test cases.

    Sample Input 

    3 
    6 8
    2 1
    1 3
    4 5
    2 4
    5 3
    2 3
    3 6
    5 6
    3 5
    2 4
    1 
    6 5
    6 8
    2 1
    1 3
    4 5
    2 4
    5 3
    2 3
    3 6
    5 6
    2 3
    3 5
    1 
    4 2
    5 4
    1 2
    2 3
    3 4
    4 5
    1 2
    4 5
    2 
    2 3
    3 4
    

    Sample Output 

    YES 
    NO 
    NO
    


    题意:给出一个无向图,然后某两条边是一定要经过的,并且每条边和每个点最多只能经过一次,你需要从某一个点出发,按上面的规则回到这个出发点,问这种路线存不存在。


    思路:我们把每个点拆成两个点,一个表示出度,一个表示入度,然后他们之间连一条容量为1的边,如果图中存在一条边(u,v) 我们就把u的出度连到v的入度,最后我们根据要求有两条边的下界容量为1,于是我们对这两条边进行带下界容量的建图方式,然后起点是x1的出度,终点是x1的入度(假设x1是必须经过的一条边的某一个点),对于这个x1的出度和入度,不要连起来。  那么我们跑一次网络流,如果所有带下界的边满流,那么就存在一种方案了,否则就不存在。

    。。。。我的代码能过UVA的,ZOJ的好像过不了。。。不知道哪里还有什么BUG


    代码:

    #include<iostream>
    #include<cstdio>
    #include<vector>
    #include<queue>
    #include<string.h>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const short inf = 1 << 14;
    const int maxn = 2000 + 10;
    
    struct Edge
    {
    	short u, v;
    	short cap;
    	short flow;
    	Edge(short u, short v, short cap, short flow)
    		:u(u), v(v), cap(cap), flow(flow) {}
    };
    
    
    vector<Edge> edges;
    vector<int> G[maxn];
    
    
    void add(short u, short v, short cap)
    {
    	edges.push_back(Edge(u, v, cap, 0));
    	edges.push_back(Edge(v, u, 0, 0));
    	int m = edges.size();
    	G[u].push_back(m - 2);
    	G[v].push_back(m - 1);
    }
    
    
    struct ISAP
    {
    	int d[maxn], p[maxn], num[maxn], cur[maxn];
    	int n, s, t;
    	void init(int n) { this->n = n; }
    
    	int Augment()
    	{
    		int x = t, a = inf;
    		while (x != s)
    		{
    			Edge&e = edges[p[x]];
    			a = min(a, e.cap - e.flow);
    			x = e.u;
    		}
    		x = t;
    		while (x != s)
    		{
    			edges[p[x]].flow += a;
    			edges[p[x] ^ 1].flow -= a;
    			x = edges[p[x]].u;
    		}
    		return a;
    	}
    
    
    	void bfs()
    	{
    		for (int i = 0; i < n; ++i) d[i] = inf;
    		queue<int> q;
    		d[t] = 0;
    		q.push(t);
    		while (q.size())
    		{
    			int x = q.front(); q.pop();
    			for (int i = 0; i<G[x].size(); ++i)
    			{
    				Edge&e = edges[G[x][i]];
    				if (e.cap>0 || d[e.v] <= d[x] + 1) continue;
    				d[e.v] = d[x] + 1;
    				q.push(e.v);
    			}
    		}
    	}
    
    
    	int maxflow(int s, int t)
    	{
    		this->s = s, this->t = t;
    		memset(num, 0, sizeof(num));
    		memset(cur, 0, sizeof(cur));
    		memset(d, 0, sizeof(d));
    		bfs();
    		for (int i = 0; i < n; ++i)
    		if (d[i] != inf) ++num[d[i]];
    		int flow = 0, x = s;
    		while (d[s] < n)
    		{
    			if (x == t)
    			{
    				flow += Augment();
    				x = s;
    			}
    			int ok = 0;
    			for (int i = cur[x]; i<G[x].size(); ++i)
    			{
    				Edge&e = edges[G[x][i]];
    				if (e.cap>e.flow&&d[e.v] + 1 == d[x])
    				{
    					ok = 1;
    					cur[x] = i;
    					p[e.v] = G[x][i];
    					x = e.v;
    					break;
    				}
    			}
    			if (!ok)
    			{
    				int m = n - 1;
    				for (int i = 0; i<G[x].size(); ++i)
    				{
    					Edge&e = edges[G[x][i]];
    					if (e.cap>e.flow) m = min(m, d[e.v]);
    				}
    				if (--num[d[x]] == 0) break;
    				++num[d[x] = m + 1];
    				cur[x] = 0;
    				if (x != s) x = edges[p[x]].u;
    			}
    		}
    		return flow;
    	}
    }solver;
    
    bool g[1010][1010];
    int N, M;
    
    inline int nodein(int x) { return 2 * x - 1; }
    inline int nodeout(int x) { return 2 * x; }
    
    void solve()
    {
    	memset(g, false, sizeof(g));
    	scanf("%d%d", &N, &M);
    	for (int i = 0; i < M; ++i)
    	{
    		int x, y; scanf("%d%d", &x, &y);
    		while (x == y);
    		g[x][y] = g[y][x] = true;
    	}
    	int x1, y1, x2, y2;
    	scanf("%d%d", &x1, &y1);
    	scanf("%d%d", &x2, &y2);
    	g[x1][y1] = g[x2][y2] = false;
    	g[y1][x1] = g[y2][x2] = false;
    	int F; scanf("%d", &F);
    	for (int i = 0; i < F; ++i)
    	{
    		int x, y; scanf("%d%d", &x, &y);
    		g[x][y] = g[y][x] = false;
    	}
    	edges.clear();
    	for (int i = 0; i < maxn; ++i) G[i].clear();
    	for (int i = 1; i <= N; ++i)
    	for (int j = i + 1; j <= N; ++j)
    	{
    		if (!g[i][j]) continue;
    		add(nodeout(i), nodein(j), 1);
    		add(nodeout(j), nodein(i), 1);
    	}
    
    	for (int i = 1; i <= N; ++i)
    	if (i != x1) add(nodein(i), nodeout(i), 1);
    
    	int s = 0, t = 2 * N + 1;
    	add(s, nodeout(x1), 1), add(nodein(x1), t, 1);
    	add(t, s, inf);
    
    	int ss = 2 * N + 2, tt = 2 * N + 3;
    	int minflow = 0;
    
    	add(ss, nodein(y1), 1);
    	add(nodeout(x1), tt, 1);
    	++minflow;
    	vector<Edge> tmp = edges;
    	add(nodeout(x2), tt, 1);
    	add(ss, nodein(y2), 1);
    	++minflow;
    	solver.init(tt + 1);
    	int ret = solver.maxflow(ss, tt);
    	/*cout << "minflow: " << minflow << endl;
    	cout << "Maxflow: " << ret << endl;*/
    	if (ret == minflow) { puts("YES"); return; }
    	//cout << edges.size() << endl;
    	for (int i = 0; i < 2; ++i)
    	{
    		Edge&e = edges.back();/*
    		cout << G[e.v].back()<<" ";*/
    		G[e.v].pop_back();
    	/*	cout << G[e.u].back() << endl;*/
    		G[e.u].pop_back();
    		edges.pop_back();
    		edges.pop_back();
    	}
    	edges = tmp;
    	add(nodeout(y2), tt, 1);
    	add(ss, nodein(x2), 1);
    	ret = solver.maxflow(ss, tt);/*
    	cout << "minflow: " << minflow << endl;
    	cout << "Maxflow: " << ret << endl;*/
    	if (ret == minflow) puts("YES");
    	else puts("NO");
    }
    
    
    int main()
    {
    	int T; cin >> T;
    	while (T--)
    	{
    		solve();
    	}
    }
    


    展开全文
  • 无源汇点有下界可行流建图方法: 对于每个点,求出流入流量下界之和和流出流量下界之和,所有边u->v的流量下界变位0,上界变位high-low。但是这样不能保证流量守恒,所以需要建立附加流量,设源点s和汇点t,对于...

    Reactor Cooling


    Time Limit: 5 Seconds      Memory Limit: 32768 KB      Special Judge


    The terrorist group leaded by a well known international terrorist Ben Bladen is buliding a nuclear reactor to produce plutonium for the nuclear bomb they are planning to create. Being the wicked computer genius of this group, you are responsible for developing the cooling system for the reactor.

    The cooling system of the reactor consists of the number of pipes that special cooling liquid flows by. Pipes are connected at special points, called nodes, each pipe has the starting node and the end point. The liquid must flow by the pipe from its start point to its end point and not in the opposite direction.

    Let the nodes be numbered from 1 to N. The cooling system must be designed so that the liquid is circulating by the pipes and the amount of the liquid coming to each node (in the unit of time) is equal to the amount of liquid leaving the node. That is, if we designate the amount of liquid going by the pipe from i-th node to j-th as fij, (put fij = 0 if there is no pipe from node i to node j), for each i the following condition must hold:

    fi,1+fi,2+...+fi,N = f1,i+f2,i+...+fN,i

    Each pipe has some finite capacity, therefore for each i and j connected by the pipe must be fij <= cij where cij is the capacity of the pipe. To provide sufficient cooling, the amount of the liquid flowing by the pipe going from i-th to j-th nodes must be at least lij, thus it must be fij >= lij.

    Given cij and lij for all pipes, find the amount fij, satisfying the conditions specified above.

     

    This problem contains multiple test cases!

    The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

    The output format consists of N output blocks. There is a blank line between output blocks.

     

    Input

    The first line of the input file contains the number N (1 <= N <= 200) - the number of nodes and and M - the number of pipes. The following M lines contain four integer number each - i, j, lij and cij each. There is at most one pipe connecting any two nodes and 0 <= lij <= cij <= 10^5 for all pipes. No pipe connects a node to itself. If there is a pipe from i-th node to j-th, there is no pipe from j-th node to i-th.

     

    Output

    On the first line of the output file print YES if there is the way to carry out reactor cooling and NO if there is none. In the first case M integers must follow, k-th number being the amount of liquid flowing by the k-th pipe. Pipes are numbered as they are given in the input file.

     

    Sample Input

    2

    4 6
    1 2 1 2
    2 3 1 2
    3 4 1 2
    4 1 1 2
    1 3 1 2
    4 2 1 2

    4 6
    1 2 1 3
    2 3 1 3
    3 4 1 3
    4 1 1 3
    1 3 1 3
    4 2 1 3

     

    Sample Input

    NO

    YES
    1
    2
    3
    2
    1
    1

     

    题意:给以个流量图,每个边的流量必须为[l,r],没有源汇点,问是否能跑出一个可行流并输出每条边的流量。

     

    无源汇点有下界可行流建图方法:

    对于每个点,求出流入流量下界之和和流出流量下界之和,所有边u->v的流量下界变位0,上界变位high-low。但是这样不能保证流量守恒,所以需要建立附加流量,设源点s和汇点t,对于所有下界流入量大于流出量的点,s与之建边,流量为两者之车,对于所有下界流入量小于流出量的点,与t建边,流量为两者之差。此时跑一边最大流,如果从源点流出的流量之和等于最大流,就说明可以流量守恒即存在可行流,那么没条边的流量等于该条边的流量下界+附加流跑出的流量。

    #include<stdio.h>
    #include<algorithm>
    #include<string.h>
    #include<string>
    #include<map>
    #include<queue>
    using namespace std;
    const int maxn = 205;
    const int maxm = 50005;
    const int INF = 1e9 + 7;
    struct node
    {
    	int u, v, flow, next, low;
    }edge[maxm];
    int n, m, s, t, cnt;
    int head[maxn], dis[maxn], pre[maxm], cur[maxm], in[maxn], out[maxn];
    char str[205][205];
    void init()
    {
    	cnt = s = 0, t = n + 1;
    	memset(head, -1, sizeof(head));
    	memset(in, 0, sizeof(in));
    	memset(out, 0, sizeof(out));
    }
    void add(int u, int v, int flow, int low)
    {
    	edge[cnt].u = u, edge[cnt].v = v, edge[cnt].flow = flow, edge[cnt].low = low;
    	edge[cnt].next = head[u], head[u] = cnt++;
    	edge[cnt].u = v, edge[cnt].v = u, edge[cnt].flow = 0, edge[cnt].low = low;
    	edge[cnt].next = head[v], head[v] = cnt++;
    }
    int bfs()
    {
    	queue<int>q;
    	memset(dis, -1, sizeof(dis));
    	dis[s] = 0;
    	q.push(s);
    	while (!q.empty())
    	{
    		int u = q.front();q.pop();
    		for (int i = head[u];i != -1;i = edge[i].next)
    		{
    			int v = edge[i].v;
    			if (dis[v] == -1 && edge[i].flow)
    			{
    				dis[v] = dis[u] + 1;
    				q.push(v);
    			}
    		}
    	}
    	if (dis[t] == -1) return 0;
    	return 1;
    }
    int dfs(int u, int flow)
    {
    	if (u == t) return flow;
    	for (int &i = cur[u];i != -1;i = edge[i].next)
    	{
    		int v = edge[i].v;
    		if (dis[v] == dis[u] + 1 && edge[i].flow)
    		{
    			int d = dfs(v, min(edge[i].flow, flow));
    			if (d > 0)
    			{
    				edge[i].flow -= d;
    				edge[i ^ 1].flow += d;
    				return d;
    			}
    		}
    	}
    	return 0;
    }
    int dinic()
    {
    	int ans = 0, d;
    	while (bfs())
    	{
    		for (int i = s;i <= t;i++) cur[i] = head[i];
    		while (d = dfs(s, INF))
    			ans += d;
    	}
    	return ans;
    }
    int main()
    {
    	int i, j, k, sum, x, T;
    	int u, v, low, high;
    	scanf("%d", &T);
    	while (T--)
    	{
    		scanf("%d%d", &n, &m);
    		init();sum = 0;
    		for (i = 1;i <= m;i++)
    		{
    			scanf("%d%d%d%d", &u, &v, &low, &high);
    			add(u, v, high - low, low);
    			in[v] += low, out[u] += low;
    		}
    		for (i = 1;i <= n;i++)
    		{
    			if (in[i] > out[i])
    			{
    				sum += in[i] - out[i];
    				add(s, i, in[i] - out[i], 0);
    			}
    			else add(i, t, out[i] - in[i], 0);
    		}
    		if (dinic() != sum)
    			printf("NO\n");
    		else
    		{
    			printf("YES\n");
    			for (i = 0;i < m * 2;i += 2)
    				printf("%d\n", edge[i ^ 1].flow + edge[i].low);
    		}
    	}
    	return 0;
    }

     

    展开全文
  • 主要是针对有上下界的网络流建图。 有上下界的网络流建图模板: { 流量上下限的无源汇的可行流建图方法: 对于有流量上下限的无源的网络流的可行流转化为一般的有源汇点的最大流来做 (1)添加超级源点S和超级汇点T ...

    sgu194 zoj3229 sgu176 zoj1994 zoj3496

    主要是针对有上下界的网络流建图。

    有上下界的网络流建图模板:

    {
    流量上下限的无源汇的可行流建图方法:
    对于有流量上下限的无源的网络流的可行流转化为一般的有源汇点的最大流来做
    (1)添加超级源点S和超级汇点T
    (2)对于原有的边(u,v,l(u,v),c(u,v))(l为流量下限,c为流量上限),添加边(u,v,0,c-l);
    (3)对于每个结点i,记w[i]=sum(l(u,i))-sum(l(i,v));//进来的的下界流量-出去的下界流
    量,若w[i]>0,添加边(S,i,w[i]),若w[i]<0,添加边(i,T,-w[i]);
    (4)求解S-T的最大流;
    (5)当且仅当S的出边和T的入边满流,原流量限制的无源网络流可行流有解;
    (6)一组可行流的解为:
    对于每条流量边(u,v),可行流量为l(u,v)+其构造的图中的流量.
      
    1.u到v建容量为C[u,v]-B[u.v]的边 //C是上界,B是下界
    2.对于点u,记tmp为in[u]-ou[u],若tmp>0,则S向u建容量为tmp的边,若tmp<0,则u向T建边
    ,容量是-tmp。//in[u]记录u的入边的流量下界和,ou[u]记录u的出边的流量的下界和
    若满流,则有解

    流量上下限的有源汇的网络流(最大流)建图方法:
    从汇点向源点建一条容量为INF的边,超级源点连i(w[i]>0),i连向超级汇点(w[i]<0),
    对超级源点和超级汇点跑一次最大流,当maxflow=(w[i]>0)的和时,则有可行流,即有解。
    有解就删除超级源点和汇点(超级源点和超级汇点之间的流量设成0,或者删除点),再对源
    点和汇点跑一次最大流maxflow=(第一次流满下界的流+第二次能流通的自由流)


    流量有上下限的有源汇的最小流建图:

    1.u到v建容量为C[u,v]-B[u.v]的边 //C是上界,B是下界
    2.对于点u,记tmp为in[u]-ou[u],若tmp>0,则S向u建容量为tmp的边,若tmp<0,则u向T建边
    ,容量是-tmp。//in[u]记录u的入边的流量下界和,ou[u]记录u的出边的流量的下界和

    先跑一遍最大流,然后源点和汇点连一条容量为inf的边,再跑一遍最大流,就是解
    }


    最大权闭合图解法:源点向正权点连边对应点权值,原图边容量inf,负权点向汇点连边权值
    绝对值,ans=正权和-最大流。 

    最大流=最小割(边)=最小割(点)

    以后自己还会逐渐更新。

    展开全文
  • 下界的最小,刘汝佳的大白上其实讲的已经很清楚了 先按照可行建图方法建图以后跑一遍,但是由于只是满足了可行并没有满足最小的要求所以我们再删除超级源和超级汇以及t->s的连边以后再倒着从t跑一遍退...

    有下界的最小流,刘汝佳的大白上其实讲的已经很清楚了

    先按照可行流的建图方法建图以后跑一遍,但是由于只是满足了可行并没有满足最小的要求所以我们再删除超级源和超级汇以及t->s的连边以后再倒着从t跑一遍退流即可。

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #define LL long long
    #define maxn 100021
    #define inf 0x3fffffff
    using namespace std;
    int n,tot=1,head[maxn],s,t,S,T,ans;
    int q[maxn],h[maxn],last[maxn],ind[maxn];
    struct edge{int v,next,w;}e[maxn];
    void adde(int a,int b,int c){
    	e[++tot].v=b;e[tot].next=head[a],e[tot].w=c;
    	head[a]=tot;
    	e[++tot].v=a;e[tot].next=head[b],e[tot].w=0;
    	head[b]=tot;
    } 
    bool bfs(){
    	int l=0,r=1;
    	for(int i=0;i<=T;i++)h[i]=-1;
    	h[S]=0,q[0]=S;
    	while(l<r){
    		int u=q[l++];
    		for(int v,i=head[u];i;i=e[i].next){
    			if(h[v=e[i].v]==-1&&e[i].w){
    				h[v]=h[u]+1;
    				q[r++]=v;
    			}
    		}
    	}return h[T]!=-1;
    }
    int dfs(int u,int f){
    	if(!f||u==T)return f;
    	int used=0,w;
    	for(int v,i=last[u];i;i=e[i].next){
    		if(h[v=e[i].v]==h[u]+1&&e[i].w){
    			last[u]=i;
    			w=min(e[i].w,f-used);
    			w=dfs(v,w);
    			used+=w;e[i].w-=w,e[i^1].w+=w;
    			if(used==f)return f;
    		}
    	}
    	if(!used)h[u]=-1;
    	return used;
    }
    int dinic(){
    	int ans=0;
    	while(bfs()){
    		for(int i=0;i<=T;i++)last[i]=head[i];
    		ans+=dfs(S,inf);
    	}return ans;
    }
    void rebuild(){
    	head[s]=e[head[s]].next;
    	head[t]=e[head[t]].next;
    	for(int i=head[S];i;i=e[i].next)
    		e[i].w=e[i^1].w=0;
    	for(int i=head[T];i;i=e[i].next)
    		e[i].w=e[i^1].w=0;
    	adde(S,t,inf);
    	adde(s,T,inf);
    }
    int main(){
    	int ans;
    	scanf("%d",&n);
    	s=n+1,t=n+2,S=n+3,T=n+4;
    	for(int cc,x,i=1;i<=n;i++){
    		scanf("%d",&cc);
    		for(int j=1;j<=cc;j++){
    			scanf("%d",&x);
    			adde(i,x,inf);
    			ind[x]++,ind[i]--;
    		}
    	}
    	for(int i=1;i<=n;i++){
    		adde(s,i,inf),adde(i,t,inf);
    		if(ind[i]>0)adde(S,i,ind[i]);
    		else adde(i,T,-ind[i]);
    	}
    	adde(t,s,inf);
    	dinic();
    	ans=e[tot].w;
    	rebuild();
    	ans-=dinic();
    	printf("%d",ans);
    	return 0;
    }


    展开全文
  • 由于各行各列的值已经知道,并且注意到矩阵横行和之和等于就矩阵竖行和之和,我们可以转化出一个流网络,节点是每一行和每一列,假想一个源节点在矩阵左边,汇节点在矩阵上方,则我们要做的就是让从源经由矩阵留到...
  • 三种简单的网络流建图

    千次阅读 2018-03-27 15:09:14
    最小费用最大问题,顾名思义,在保证网络流量最大的前提下,使得花费最小。如n辆卡车要运送物品,从A地到B地。由于每条路段都有不同的路费要缴纳,每条路能容纳的车的数量有限制,最小费用最大问题指如何分配...
  • 2.求有源有汇有下界最大 建图与上面一样,把原来的汇点向源点连边INF 之后先求一遍可行 之后再割掉t-s的边去求最大 最终的答案即dinic+e[t--->s].flow(就是求可行的时候的流量)     然后来...
  • 首先建图里面需要有刘汝佳白书里的无源无汇有容量下界网络的最大(P366)的知识,可以看一下,估计第一次也不是很懂,看完之后可以再看下面的建图,估计会懂很多。 总的思路是S->带有行值的黑格子->白色格子->...
  • UVa 1440 只有下界的最小

    千次阅读 2013-07-21 16:48:20
    题意: 给你一幅有向图,你每次可以从任意点出发。图中的每条边至少要经过一次,问你至少要走几次。 建图: 设每个点i的入度减去出度为d[i], S为源点,T为汇点。...显然,对于没有下界网络 其最小
  • 题很长,但其实就是给个有源汇带下界网络流(+是源,-是汇),求最小流 求法: 1.模仿可行流建图,但是不加t到s的INF边 2.跑最大流 3.加t到sINF边 4.跑最大流 5.如果两次答案相加不等于sum,无解; 6.如果有解...
  • 最大流建图习题

    2017-11-23 13:36:37
    Lightoj 1154题意: 二维坐标上有N()个点, 每个点有两个值,一个值是在这个点上的企鹅数量,另一个值是能从这个点跳到另...具体建图呢?比如u有多个点a,b,c可以到达,肯定不可能是u和a,b,c都连一条边然后容量设置成限
  • UVA1440 有下界的最小

    千次阅读 2014-10-22 21:14:01
    这个转化为网络流的话,就相当于 求一个最小流,并且存在下界,即每条边至少走一次 这让我联想到很久之前的一道题,也是有向图,问走多少条路径可以将整个图中的每条边都走过,但是跟本题不同的是,那题是不允许...
  • 概述 有上下界的网络流建图 网络流有了建图,其他都是浮云。设立超级源和超级汇
  • POJ 2396 Budget 带下界的最大 Dinic

    千次阅读 2011-07-12 20:44:08
    =sum) //附加网络的最大不等于所有下界之和,则无解 { printf("IMPOSSIBLE\n"); return; } cap[t][s]=cap[s][t]=0; //去掉边(t,s)和(s,t) res=dinic(s,t,num); //在对去边及超级汇源之后的图求解最大 for...
  • 上下界网络流

    2017-01-23 23:42:22
    最近几天学习了上下界网络流,感觉不太懂,但至少学会了如何建图。总的来说,分为以下三个问题无源汇最大流 有源汇最大流 有源汇最小流一、无源汇最大流 大致的做法是这样的: 首先构成一个附加网络:将图的下界...
  • 1.新建源汇SS,TT,按有上下界的方法建图. 2.做一次SS-&gt;TT的最大. 3.原图中的汇点T向原图中的源点S连一条inf的边. 4.再做一次SS&gt;TT的最大就是答案. #include &lt;bits/stdc++.h&gt; ...
  • 然后发现是带下界网络流,这样一下这道题就挺傻逼的了。 对于一条边(x,y,z)表示从x到y,费用为z 那么建图: addedge(S,y,1,z)表示至少经过一次 addedge(x,y,inf,z)随便经过 addedge(x,1,inf,0)回到1点 ...
  • 对于求解无源汇带上下界的网络流,我们可以这样建图建图模型:以前写的最大流默认的下界为0,而这里的下界却不为0,所以我们要进行再构造让每条边的下界为0,这样做是为了方便处理。对于每根管子有一个上界容量up...
  • 题目大意:主人公在玩游戏,他的存档系统坏了,只能从头开始游戏,不能从中途...裸的有下界有源汇的费用。我也不知道为什么要那样建图。。 CODE: #include #include #include #include #include #defi
  • 网络流】之有上下限的网络流

    千次阅读 2012-08-28 16:34:25
    网络流】之有上下限的网络流 发表于 2011/09/04 由 starfall 有上下限的网络流其实很简单。只要掌握建图方法就可以了。   我碰到过的有上下限的网络流题目只分三种情况: 1、是否存在可行流...
  • 网络流

    2017-02-22 22:27:47
    网络流
  • HUST 1342 Cheat Secretly 有源汇上下界网络流 最小流题意:有N个点M条边的单向无环图,先要求必须走某些边,走到没有出边的点可以转移到任意一个点,问最少转移的次数。最小流建图 入度为0的连st 流量为oooo 出度...
  • 最近两个月在做《线性规划与网络流24题》这套题,加深了对网络流的理解。涵盖到的模型有:二分图匹配、二分图的最大独立集、最大权闭合图、有向无环图的最小路径覆盖、最多不相交路径、最大权不相交路径、区间k覆盖...
  • 网络流小结

    2019-10-05 12:35:46
    有上下界限制网络流建图 115. 无源汇有上下界可行流 116. 有源汇有上下界最大流 117. 有源汇有上下界最小流 板子题:洛谷P3376 @ 有上下界限制网络流建图 无源汇有上下界可行流 设下界为B,上界为C。.....
  • 对于有下界网络流,首先要想办法去掉下界,做法是把原图中的流量分成流b和f’,其中b的流量为原流量下界,f′=f−bf'=f-b。 虚拟一个源点s和一个汇点t,对每个点u,设D(u)=∑bin−∑boutD(u)=\sum_{}b_{in}-\sum_{...
  • 【自用】有上下界的网络流

    千次阅读 2015-04-24 09:39:19
    无源汇网络流(有向图): 最终的最大流需要是一个循环体,流量在内部循环流动。 必须流和自由流的定义: 首先设每条边上界为flow,下界为low,那么就存在low的必须流和flow-low的自由流。 「无源汇」有上下界...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 496
精华内容 198
关键字:

下界建图网络流