【 POJ - 3801】Crazy Circuits(有源汇、上下界最小流)
Description
You’ve just built a circuit board for your new robot, and now you need to power it. Your robot circuit consists of a number of electrical components that each require a certain amount of current to operate. Every component has a + and a − lead, which are connected on the circuit board at junctions. Current flows through the component from + to − (but note that a component does not “use up” the current: everything that comes in through the + end goes out the − end).The junctions on the board are labeled 1, ..., N, except for two special junctions labeled + and − where the power supply terminals are connected. The + terminal only connects + leads, and the − terminal only connects − leads. All current that enters a junction from the − leads of connected components exits through connected + leads, but you are able to control how much current flows to each connected + lead at every junction (though methods for doing so are beyond the scope of this problem). Moreover, you know you have assembled the circuit in such a way that there are no feedback loops (components chained in a manner that allows current to flow in a loop).
Figure 1: Examples of two valid circuit diagrams. In (a), all components can be powered along directed paths from the positive terminal to the negative terminal. In (b), components 4 and 6 cannot be powered, since there is no directed path from junction 4 to the negative terminal.In the interest of saving power, and also to ensure that your circuit does not overheat, you would like to use as little current as possible to get your robot to work. What is the smallest amount of current that you need to put through the + terminal (which you can imagine all necessarily leaving through the − terminal) so that every component on your robot receives its required supply of current to function?
Input
The input file will contain multiple test cases. Each test case begins with a single line containing two integers: N (0 ≤ N ≤ 50), the number of junctions not including the positive and negative terminals, and M (1 ≤ M ≤ 200), the number of components in the circuit diagram. The next M lines each contain a description of some component in the diagram. The ith component description contains three fields: pi, the positive junction to which the component is connected, ni, the negative junction to which the component is connected, and an integer Ii (1 ≤ Ii ≤ 100), the minimum amount of current required for component i to function. The junctions pi and ni are specified as either the character ‘+’ indicating the positive terminal, the character ‘-’ indicating the negative terminal, or an integer (between 1 and N) indicating one of the numbered junctions. No two components have the same positive junction and the same negative junction. The end-of-file is denoted by an invalid test case with N = M = 0 and should not be processed.Output
For each input test case, your program should print out either a single integer indicating the minimum amount of current that must be supplied at the positive terminal in order to ensure that every component is powered, or the message “impossible” if there is no way to direct a sufficient amount of current to each component simultaneously.Sample Input
6 10
+ 1 1
1 2 1
1 3 2
2 4 5
+ - 1
4 3 2
3 5 5
4 6 2
5 - 1
6 5 3
4 6
+ 1 8
1 2 4
1 3 5
2 4 6
3 - 1
3 4 3
0 0Sample Output
9
impossibleHint
For those who are electronics-inclined, imagine that you have the ability to adjust the potential on any component without altering its current requirement, or equivalently that there is an accurate variable potentiometer connected in series with each component that you can adjust. Your power supply will have ample potential for the circuit.
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 1010
#define Maxm 100100
#define INF 0xfffffff char s[];
int stt,edd;
int first[Maxn],dis[Maxn];
int sum; struct node
{
int x,y,f,o,next;
}t[Maxm];int len; int mymin(int x,int y) {return x<y?x:y;} void ins(int x,int y,int f)
{
if(x==stt) sum+=f;
t[++len].x=x;t[len].y=y;t[len].f=f;
t[len].next=first[x];first[x]=len;t[len].o=len+;
t[++len].x=y;t[len].y=x;t[len].f=;
t[len].next=first[y];first[y]=len;t[len].o=len-;
} void make_edge(int x,int y,int k1,int k2)
{
ins(stt,y,k1);
ins(x,edd,k1);
ins(x,y,k2-k1);
} queue<int > q;
bool bfs(int st,int ed)
{
while(!q.empty()) q.pop();
memset(dis,-,sizeof(dis));
q.push(st);dis[st]=;
while(!q.empty())
{
int x=q.front();
for(int i=first[x];i;i=t[i].next) if(t[i].f>)
{
int y=t[i].y;
if(dis[y]==-)
{
dis[y]=dis[x]+;
q.push(y);
}
}
q.pop();
}
if(dis[ed]!=-) return ;
return ;
} int ffind(int x,int ed,int flow)
{
if(x==ed) return flow;
int now=;
for(int i=first[x];i;i=t[i].next) if(t[i].f>)
{
int y=t[i].y;
if(dis[y]==dis[x]+)
{
int a=ffind(y,ed,mymin(flow-now,t[i].f));
t[i].f-=a;
t[t[i].o].f+=a;
now+=a;
if(now==flow) break;
}
}
if(now==) dis[x]=-;
return now;
} int max_flow(int st,int ed)
{
int ans=;
while(bfs(st,ed))
{
ans+=ffind(st,ed,INF);
}
if(ans!=sum) return -;
return ans;
} int main()
{
int n,m;
while()
{
scanf("%d%d",&n,&m);
if(n==&&m==) break;
int st=n+,ed=st+;len=;
stt=ed+;edd=stt+;sum=;
memset(first,,sizeof(first));
for(int i=;i<=m;i++)
{
int x,y;
scanf("%s",s);
if(s[]=='+') x=st;
else if(s[]=='-') x=ed;
else
{
int now=;x=;
while(s[now]>=''&&s[now]<='') x=x*+s[now++]-'';
}scanf("%s",s);
if(s[]=='+') y=st;
else if(s[]=='-') y=ed;
else
{
int now=;y=;
while(s[now]>=''&&s[now]<='') y=y*+s[now++]-'';
}
int c;
scanf("%d",&c);
make_edge(x,y,c,INF);
}
int id=len+;
ins(ed,st,INF);
int now=max_flow(stt,edd);
if(now==-) printf("impossible\n");
else
{
printf("%d\n",t[id].f);
}
}
return ;
}
[POJ3801]
2016-06-13 13:12:16
最新文章
- Twitter面试题蓄水池蓄水量算法(原创 JS版,以后可能会补上C#的)
- TranslateAnimation 运行动画后实际位置不正确问题
- win7 下配置Openssl
- C#解leetcode 228. Summary Ranges Easy
- 12 Integer to Roman(int转罗马数字Medium)
- NuGet学习笔记(3)——搭建属于自己的NuGet服务器(转)
- 给c++程序员的一份礼物——常用工具集
- Hadoop 2.6.5 FileSystem和Configuration两个对象的探究
- 如何高效的学习WEB前端
- 荣耀7.0系统手机最简单激活Xposed框架的步骤
- Isight Linux 2016hf2 安装步骤
- Scrapy 框架 CrawlSpider 全站数据爬取
- 2018年度 35 个最好用 Vue 开源库
- 【Java】maven多项目资源共享
- WEB服务器、HTTP服务器、应用服务器、IIS
- [20180122]列统计与直方图.txt
- (1.10)SQL优化——mysql 常见SQL优化
- struts2应用
- WPF 捕捉全局异常
- 鼠标经过显示二级菜单的js特效
热门文章
- 【NodeJs】用arrayObject.join(&#39;&#39;)处理粘包的错误原因
- asp.net中ScriptManager自带Ajax与jQuery事件冲突
- C++ 读取XML文件(tinyXML库的应用)
- div随另一个div自动增高
- Jquery Ajax方法传递json到action
- WEB 开发工具分享
- [XML] C#XMLProcess操作Xml文档的帮助类 (转载)
- SQL学习:主键,外键,主键表,外键表,数据库的表与表之间的关系;
- 本地tomcat的start.bat启动时访问不出现小猫图标
- ios开发中MVC模式的理解