首页 > 搜索 > DFS搜索 > HDU 3157-Crazy Circuits-BFS-[解题报告]HOJ
2014
03-06

HDU 3157-Crazy Circuits-BFS-[解题报告]HOJ

Crazy Circuits

问题描述 :

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 problem1). 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).

Repair Depots

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?

Hint

1 For those who are electronics-inclined, imagine that you have the ability to adjust the potential on any componentwithout 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.

输入:

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.

输出:

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.

样例输入:

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 0

样例输出:

9 
impossible

白书二代上提到了无源无汇有容量下界网络可行流和有容量下界网络的s-t最大/最小流问题。

但是由于本人智商捉鸡,觉得LRJ大神写的似乎不是很好理解,所以只能找一些题目来帮助自己理解理解了。

这里直说方法,证明。。。不会。

1.无源无汇有容量下界可行流

这个问题的解法在周源的那个论文里讲的很清楚了。

对于每条边,都有一个容量下界b和一个容量上界c,那么这条边实际的可行流量只有c-b,剩下的b必须满流。

对每个点i,求a = sum(流向它的下界流)-sum(从它流出的下界流量)

若a>0,从源点0连一条到i的容量为a的边

若a<0,从i连一条到汇点n+1的容量为-a的边

(我觉得其实这里都是为求自由流做的准备)

然后求一次最大流,若所有从源点出发的点都满流,则有可行流,每条边的可行流为求最大流后的实际流量flow+该边的流量下界b

题目:ZOJ 2314

代码:

#include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <vector>
 #include <queue>
 #define maxn 210
 #define INF 100000000
 using namespace std;
 
 struct Edge{
     int from,to,cap,flow;
 };
 
 struct Dinic{
     int n,m,s,t;
     vector<Edge> edges;
     vector<int> G[maxn];
     bool vis[maxn];
     int d[maxn];
     int cur[maxn];
 
     void ClearAll(int n){
         for(int i = 0;i < n;i++)    G[i].clear();
         edges.clear();
     }
 
     void add_edge(int from,int to,int cap){
         edges.push_back((Edge){from,to,cap,0});
         edges.push_back((Edge){to,from,0,0});
         m = edges.size();
         G[from].push_back(m-2);
         G[to].push_back(m-1);
     }
 
     bool BFS(){
         memset(vis,0,sizeof(vis));
         queue<int> Q;
         Q.push(s);
         vis[s] = 1;
         d[s] = 0;
         while(!Q.empty()){
             int x = Q.front();Q.pop();
             for(int i = 0;i < G[x].size();i++){
                 Edge& e = edges[G[x][i]];
                 if(!vis[e.to] && e.cap > e.flow){
                     vis[e.to] = 1;
                     d[e.to] = d[x] + 1;
                     Q.push(e.to);
                 }
             }
         }
         return vis[t];
     }
 
     int DFS(int x,int a){
         if(x == t || a == 0)    return a;
         int flow = 0,f;
         for(int &i = cur[x];i < G[x].size();i++){
             Edge& e = edges[G[x][i]];
             if(d[x] + 1 == d[e.to] && (f = DFS(e.to,min(a,e.cap-e.flow))) > 0){
                 e.flow += f;
                 edges[G[x][i]^1].flow -= f;
                 flow += f;
                 a -= f;
                 if(a == 0)  break;
             }
         }
         return flow;
     }
 
     int Maxflow(int s,int t){
         this->s = s;this->t = t;
         int flow = 0;
         while(BFS()){
             memset(cur,0,sizeof(cur));
             flow += DFS(s,INF);
         }
         return flow;
     }
 };
 
 Dinic g;
 int in[maxn],flow[50000],low[50000];
 int main()
 {
     int T,n,m,a,b,c;
     scanf("%d",&T);
     while(T--){
         scanf("%d%d",&n,&m);
         memset(in,0,sizeof(in));
         g.ClearAll(n+2);
         for(int i = 0;i < m;i++){
             scanf("%d%d%d%d",&a,&b,&low[i],&c);
             in[a] -= low[i];
             in[b] += low[i];
             g.add_edge(a,b,c-low[i]);
         }
         for(int i = 1;i <= n;i++){
             if(in[i] > 0)   g.add_edge(0,i,in[i]);
             if(in[i] < 0)   g.add_edge(i,n+1,-in[i]);
         }
         g.Maxflow(0,n+1);
         bool flag = true;
         for(int i = 0;i < g.G[0].size();i++){
             //printf("%d %d\n",g.edges[g.G[0][i]].cap,g.edges[g.G[0][i]].flow);
             if(g.edges[g.G[0][i]].flow != g.edges[g.G[0][i]].cap){
                 flag = false;
                 break;
             }
         }
         if(flag){
             printf("YES\n");
             for(int i = 0;i < m;i++){
                 printf("%d\n",low[i] + g.edges[i*2].flow);
             }
         }else{
             printf("NO\n");
         }
         printf("\n");
     }
     return 0;
 }

2.有源汇有下界的最大流问题

(1)首先假设真正的源点和汇点分别为s和t,跟上面一样:

对于每条边,都有一个容量下界b和一个容量上界c,那么这条边实际的可行流量只有c-b,剩下的b必须满流。

对每个点i,求a = sum(流向它的下界流)-sum(从它流出的下界流量)

(2)添加一条从汇点t到源点s,流量为INF的边

(3)对所有的点,根据该a值( a = sum(流向它的下界流)-sum(从它流出的下界流量) )向新构造出的源点SS,汇点TT加边

若a>0,从新源点SS连一条到i的容量为a的边

若a<0,从i连一条到新汇点TT的容量为-a的边

(4)求一次从(SS->TT)的最大流,看从SS出发的边是否全部满流,若不满流则无解

(5)删掉SS、TT这两个点

(6)再做一次(s->t)的最大流,此时各条边上的流量flow+该边的流量下限就是整个网络流量有解时的真实流量

题目:ZOJ 3229

代码:

#include <iostream>
 #include <cstdio>
 #include <vector>
 #include <cstring>
 #include <queue>
 #include <algorithm>
 #define maxn 1400
 #define INF 1000000000
 using namespace std;
 int g[1010],c[400],D[400];
 int L[400][1010],R[400][1010],T[400][1000],task[400];
 int in[maxn];
 struct Edge{
     int from,to,cap,flow;
 };
 
 struct ISAP {
   int n, m, s, t;
   vector<Edge> edges;
   vector<int> G[maxn];
   bool vis[maxn];
   int d[maxn];
   int cur[maxn];
   int p[maxn];
   int num[maxn];
 
   void AddEdge(int from, int to, int cap) {
     edges.push_back((Edge){from, to, cap, 0});
     edges.push_back((Edge){to, from, 0, 0});
     m = edges.size();
     G[from].push_back(m-2);
     G[to].push_back(m-1);
   }
 
   bool BFS() {
     memset(vis, 0, sizeof(vis));
     queue<int> Q;
     Q.push(t);
     vis[t] = 1;
     d[t] = 0;
     while(!Q.empty()) {
       int x = Q.front(); Q.pop();
       for(int i = 0; i < G[x].size(); i++) {
         Edge& e = edges[G[x][i]^1];
         if(!vis[e.from] && e.cap > e.flow) {
           vis[e.from] = 1;
           d[e.from] = d[x] + 1;
           Q.push(e.from);
         }
       }
     }
     return vis[s];
   }
 
   void ClearAll(int n) {
     this->n = n;
     for(int i = 0; i < n; i++) G[i].clear();
     edges.clear();
   }
 
   int Augment() {
     int x = t, a = INF;
     while(x != s) {
       Edge& e = edges[p[x]];
       a = min(a, e.cap-e.flow);
       x = edges[p[x]].from;
     }
     x = t;
     while(x != s) {
       edges[p[x]].flow += a;
       edges[p[x]^1].flow -= a;
       x = edges[p[x]].from;
     }
     return a;
   }
 
   int Maxflow(int s, int t) {
     this->s = s; this->t = t;
     int flow = 0;
     BFS();
     memset(num, 0, sizeof(num));
     for(int i = 0; i < n; i++) num[d[i]]++;
     int x = s;
     memset(cur, 0, sizeof(cur));
     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[x] == d[e.to] + 1) { // Advance
           ok = 1;
           p[e.to] = G[x][i];
           cur[x] = i;
           x = e.to;
           break;
         }
       }
       if(!ok) { // Retreat
         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.to]);
         }
         if(--num[d[x]] == 0) break;
         num[d[x] = m+1]++;
         cur[x] = 0;
         if(x != s) x = edges[p[x]].from;
       }
     }
     return flow;
   }
 };
 
 ISAP sap;
 int main()
 {
     int n,m;
     while(scanf("%d%d",&n,&m) == 2){
         sap.ClearAll(n+m+5);
         memset(in,0,sizeof(in));
         for(int i = 1;i <= m;i++)
             scanf("%d",&g[i]);
         for(int day = 1;day <= n;day++){
             scanf("%d%d",&task[day],&D[day]);
             for(int i = 1;i <= task[day];i++){
                 int girl_num,l,r;
                 scanf("%d%d%d",&girl_num,&l,&r);
                 girl_num++;
                 T[day][i] = girl_num;
                 L[day][girl_num] = l;
                 R[day][girl_num] = r;
             }
         }
         int s = 0,t = n+m+1;
         int SS = t+1,TT = SS + 1;
         for(int i = 1;i <= n;i++){
             for(int j = 1;j <= task[i];j++){
                 int girl_num = T[i][j];
                 in[i] -= L[i][girl_num];
                 in[n+girl_num] += L[i][girl_num];
                 sap.AddEdge(i,n+girl_num,R[i][girl_num]-L[i][girl_num]);
             }
         }
         for(int i = 1;i <= n;i++){
             sap.AddEdge(s,i,D[i]);
         }
         for(int i = 1;i <= m;i++){
             in[n+i] -= g[i];
             in[t] += g[i];
             sap.AddEdge(n+i,t,INF-g[i]);
         }
         sap.AddEdge(t,s,INF);
         int sum = 0;
         int tmp = sap.edges.size();
         for(int i = 0;i <= n+m+1;i++){
             if(in[i] > 0)   sap.AddEdge(SS,i,in[i]);
             if(in[i] < 0)   sap.AddEdge(i,TT,-in[i]);
             if(in[i] > 0)   sum += in[i];
         }
         int maxflow = sap.Maxflow(SS,TT);
         if(maxflow != sum){
             printf("-1\n\n");
             continue;
         }
         for(int i = tmp;i < sap.edges.size();i++){
             sap.edges[i].flow = sap.edges[i].cap = 0;
         }
         maxflow = sap.Maxflow(s,t);
         printf("%d\n",maxflow);
         int cnt = 0;
         for(int i = 1;i <= n;i++){
             for(int j = 1;j <= task[i];j++){
                 printf("%d\n",sap.edges[cnt*2].flow+L[i][T[i][j]]);
                 cnt++;
             }
         }
         printf("\n");
     }
     return 0;
 }

3.有源汇有下界的最小流问题

(1)如2中的(1)(3),构造网络………………

(2)这时不能直接添加一条从汇点t到源点s,流量为INF的边!要先求一次(SS->TT)的最大流,求得最大流maxflow记为flow1

(3)添加一条从汇点t到源点s,流量为INF的边

(4)再求一次从(SS->TT)的最大流,求得最大流maxflow记为flow2

(5)假如flow1+flow2==sum(sum就是所有a>0的点的a值的和,就是SS满流情况),有解

(6)此时,最小流就是t->s边上的流量

题目:HDU 3157

代码:

#include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <vector>
 #include <queue>
 #include <algorithm>
 #define maxn 60
 #define INF 1000000000
 using namespace std;
 struct Edge{
     int from,to,cap,flow;
 };
 struct Dinic{
     int n,m,s,t;
     vector<Edge> edges;
     vector<int> G[maxn];
     bool vis[maxn];
     int d[maxn];
     int cur[maxn];
     void ClearAll(int n){
         for(int i = 0;i < n;i++)    G[i].clear();
         edges.clear();
     }
     void AddEdge(int from,int to,int cap){
         edges.push_back((Edge){from,to,cap,0});
         edges.push_back((Edge){to,from,0,0});
         m = edges.size();
         G[from].push_back(m-2);
         G[to].push_back(m-1);
     }
     bool BFS(){
         memset(vis,0,sizeof(vis));
         queue<int> Q;
         Q.push(s);
         vis[s] = 1;
         d[s] = 0;
         while(!Q.empty()){
             int x = Q.front();Q.pop();
             for(int i = 0;i < G[x].size();i++){
                 Edge& e = edges[G[x][i]];
                 if(!vis[e.to] && e.cap > e.flow){
                     vis[e.to] = 1;
                     d[e.to] = d[x] + 1;
                     Q.push(e.to);
                 }
             }
         }
         return vis[t];
     }
     int DFS(int x,int a){
         if(x == t || a == 0)    return a;
         int flow = 0,f;
         for(int& i = cur[x];i < G[x].size();i++){
             Edge& e = edges[G[x][i]];
             if(d[x] + 1 == d[e.to] && (f = DFS(e.to,min(a,e.cap-e.flow))) > 0){
                 e.flow += f;
                 edges[G[x][i]^1].flow -= f;
                 flow += f;
                 a -= f;
                 if(a == 0)  break;
             }
         }
         return flow;
     }
     int Maxflow(int s,int t){
         this->s = s;this->t = t;
         int flow = 0;
         while(BFS()){
             memset(cur,0,sizeof(cur));
             flow += DFS(s,INF);
         }
         return flow;
     }
 };
 Dinic g;
 int in[maxn];
 int main()
 {
     int n,m,s,t,SS,TT,a,b,cir;
     char from[10],to[10];
     while(scanf("%d%d",&n,&m),n+m){
         memset(in,0,sizeof(in));
         g.ClearAll(n+5);
         s = 0,t = n+1,SS = t+1,TT = SS+1;
         int sum = 0;
         for(int i = 0;i < m;i++){
             scanf("%s%s%d",from,to,&cir);
             if(from[0] == '+')  a = s;
             else    sscanf(from,"%d",&a);
             if(to[0] == '-')    b = t;
             else    sscanf(to,"%d",&b);
             in[a] -= cir;in[b] += cir;
             g.AddEdge(a,b,INF-cir);
         }
         for(int i = 0;i <= t;i++){
             if(in[i] > 0)   g.AddEdge(SS,i,in[i]),sum += in[i];
             if(in[i] < 0)   g.AddEdge(i,TT,-in[i]);
         }
 
         int flow1 = g.Maxflow(SS,TT);
         g.AddEdge(t,s,INF);
         int flow2 = g.Maxflow(SS,TT);
         if(flow1 + flow2 != sum)    printf("impossible\n");
         else{
             int e = g.edges.size() - 2;
             printf("%d\n",g.edges[e].flow);
         }
     }
     return 0;
 }

 

参考:http://www.cnblogs.com/zhexipinnong/archive/2013/08/06/3241852.html


, ,
  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }