UVa11248 Frequency Hopping（最大流+最小割）

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<vector>
  5 #include<algorithm>
  6 using namespace std;
  7 
  8 const int maxn = 100+10;
  9 const int INF = 1e9*2+10;
 10 
 11 struct Edge{
 12     int u,v,cap,flow;
 13     bool operator<(const Edge& rhs) const{
 14         return u<rhs.u || (u==rhs.u && v<rhs.v) ;
 15     }
 16 };
 17 struct Dinic {
 18     int n,m,s,t;
 19     bool vis[maxn];
 20     int d[maxn],cur[maxn];
 21     vector<int> G[maxn];
 22     vector<Edge> es;
 23     
 24     void init(int n) {
 25         this->n=n;
 26         es.clear();
 27         for(int i=0;i<n;i++) G[i].clear();
 28     }
 29     void clearflow() {
 30         for(int i=0;i<es.size();i++) es[i].flow=0;
 31     }
 32     void AddEdge(int u,int v,int cap) {
 33         es.push_back((Edge){u,v,cap,0});
 34         es.push_back((Edge){v,u,0,0});
 35         m=es.size();
 36         G[u].push_back(m-2);
 37         G[v].push_back(m-1);
 38     }
 39     
 40     bool BFS() {
 41         queue<int> q;
 42         memset(vis,0,sizeof(vis));
 43         q.push(s); vis[s]=1; d[s]=0;
 44         while(!q.empty()) {
 45             int u=q.front(); q.pop();
 46             for(int i=0;i<G[u].size();i++) {
 47                 Edge& e=es[G[u][i]];
 48                 int v=e.v;
 49                 if(!vis[v] && e.cap>e.flow) {
 50                     vis[v]=1;
 51                     d[v]=d[u]+1;
 52                     q.push(v);
 53                 }
 54             }
 55         }
 56         return vis[t];
 57     }
 58     int DFS(int u,int a) {
 59         if(u==t || a==0) return a;
 60         int flow=0,f;
 61         for(int& i=cur[u];i<G[u].size();i++){
 62             Edge& e=es[G[u][i]];
 63             int v=e.v;
 64             if( d[v]==d[u]+1 && (f=DFS(v,min(a,e.cap-e.flow)))>0 ) {
 65                 e.flow+=f;
 66                 es[G[u][i]^1].flow-=f;
 67                 flow+=f,a-=f;
 68                 if(!a) break;
 69             }
 70         }
 71         return flow;
 72     }
 73     int Maxflow(int s,int t,int limit) {
 74         this->s=s , this->t=t;
 75         int flow=0;
 76         while(BFS() && flow<limit) {
 77             memset(cur,0,sizeof(cur));
 78             flow+=DFS(s,INF);
 79         }
 80         return flow;
 81     }
 82     vector<int> Mincut() {
 83         vector<int> ans;
 84         for(int i=0;i<es.size();i++)
 85             if(es[i].cap!=0 && es[i].cap==es[i].flow)
 86                  ans.push_back(i);
 87         return ans;
 88     }
 89     void reduce() {
 90         for(int i=0;i<es.size();i++) es[i].cap-=es[i].flow;
 91     }
 92 }dc;
 93 
 94 int n,m,C;
 95 
 96 int main() {
 97     int kase=0;
 98     while(scanf("%d%d%d",&n,&m,&C)==3 && n) {
 99         dc.init(n);
100         int u,v,w;
101         for(int i=0;i<m;i++) {
102             scanf("%d%d%d",&u,&v,&w);
103             u--,v--;
104             dc.AddEdge(u,v,w);
105         }
106         int flow=dc.Maxflow(0,n-1,INF);
107         printf("Case %d: ",++kase);
108         if(flow>=C) printf("possible\n");
109         else {
110             vector<int> cut;
111             vector<Edge> ans;
112             cut=dc.Mincut();
113             dc.reduce();            //考虑除去最大流之后的剩余网络//即在原流基础上增广 
114             for(int i=0;i<cut.size();i++) {
115                 dc.clearflow();
116                 Edge& e=dc.es[cut[i]];
117                 int tmp=e.cap;
118                 e.cap=C;
119                 if(flow+dc.Maxflow(0,n-1,C-flow)>=C) ans.push_back(e);
120                 e.cap=tmp;
121             }
122             if(!ans.size()) printf("not possible\n");
123             else {
124                 sort(ans.begin(),ans.end());
125                 printf("possible option:");
126                 int d=ans.size();
127                 for(int i=0;i<d-1;i++) printf("(%d,%d),",ans[i].u+1,ans[i].v+1); 
128                 printf("(%d,%d)\n",ans[d-1].u+1,ans[d-1].v+1);
129             }
130         }
131     }
132     return 0;
133 }