UVA 1658 Admiral 海上将军（最小费用流，拆点）

题意：

　　一个有v个点的有向图，要从点1到点v需要找两条路径，两路径不可经过同一个点（除了1和v点）。求这两条路径的最小费用（保证有解）。

分析：

　　难在建图，其他套模板。

　　此图给的是超级复杂图，两个点之间有多条有向边，方向还可能是相反的。用网络流来做不能仅靠2点流来保证，因为当只有3个点，4条边都是1->2->3这样的，是不是刚好2条路径？也满足了2点流的限制。其实不能这样，要保证经过每个点1点流量，还得拆点，将2~v-1这些点都拆两个点，两点之间有条费用为0容量为1的边，这样就能保证了。然后源点1出发，汇点v结束，都是流量为2就行了。当然源点，汇点需要自己另外建。

 #include <bits/stdc++.h>

 #define LL long long

 #define pii pair<int,int>

 #define INF 0x7f7f7f7f

 using namespace std;

 const int N=+;

 struct node

 {

     int from;

     int to;

     int val;

     int cap;

     int flow;

 }edge[N*N];

 int edge_cnt, ans_cost;

 int flow[N], cost[N], path[N], inq[N];

 vector<int> vect[N];

 void add_node(int from,int to,int val,int cap,int flow)

 {

     edge[edge_cnt].from=from;

     edge[edge_cnt].to=to;

     edge[edge_cnt].val=val;

     edge[edge_cnt].cap=cap;

     edge[edge_cnt].flow=flow;

     vect[from].push_back(edge_cnt++);

 }

 int spfa(int s,int e)

 {

     deque<int> que(,s);

     inq[s]=;

     cost[s]=;

     flow[s]=INF;

     while(!que.empty())

     {

         int x=que.front();

         que.pop_front();

         inq[x]=;

         for(int i=; i<vect[x].size(); i++)

         {

             node e=edge[vect[x][i]];

             if(e.cap>e.flow && cost[e.to]>cost[e.from]+e.val)

             {

                 flow[e.to]=min(flow[e.from],e.cap-e.flow);

                 cost[e.to]=cost[e.from]+e.val;

                 path[e.to]=vect[x][i];

                 if(!inq[e.to])

                 {

                     inq[e.to]=;

                     que.push_back(e.to);

                 }

             }

         }

     }

     return flow[e];

 }

 int cal(int s,int e)

 {

     int ans_flow=;

     while(true)

     {

         memset(flow, , sizeof(flow));

         memset(path, , sizeof(path));

         memset(cost, 0x7f, sizeof(cost));

         memset(inq, , sizeof(inq));

         int tmp=spfa(s, e);

         if(!tmp)    return ans_cost;

         ans_cost+=cost[e];

         ans_flow+=tmp;

         int ed=e;

         while(ed!=s)

         {

             int t=path[ed];

             edge[t].flow+=tmp;

             edge[t^].flow-=tmp;

             ed=edge[t].from;

         }

     }

 }

 int main()

 {

     freopen("input.txt", "r", stdin);

     int n, m, a, b, c;

     while(~scanf("%d%d",&n,&m))

     {

         ans_cost=;

         edge_cnt=;

         for(int i=n+; i>=; i-- )    vect[i].clear();

         memset(edge,,sizeof(edge));

         for(int i=; i<n; i++)

         {

             add_node(i*,i*+,,,);

             add_node(i*+,i*,,,);

         }

         for(int i=; i<m; i++)

         {

             scanf("%d%d%d", &a, &b, &c);

             add_node(a*+, b*, c, , );

             add_node(b*, a*+, -c, , );

         }

         add_node(, *+, , , );  //源点。2点流量

         add_node(*+, , , , );

         add_node(n*, n*+, , , );//汇点

         add_node(n*+, n*, , , );

         printf("%d\n",cal(, n*+));

     }

     return ;

 }

AC代码

巴特西

UVA 1658 Admiral 海上将军（最小费用流，拆点）

最新文章

热门文章