1、Educational Codeforces Round 29 F.Almost Permutation
（见CF题记《Educational Codeforces Round 29》）
2、uva 11613 Acme Corporation
题意：有M月，X元素每个月单位保存费用为I，在每个月中，单位生产成本为ni,最大生产数目为mi,单位销售价格为pi,最大销售限制为si,当月生产的X元素最多保存Ei个月份（比如i=1,Ei=3,则可保存月份为1,2,3,4，当月卖出当然不用存储，保存费用为0）。求最大利润？
思路：采用最小费用最小流，因为本题求最大利润，所有的消耗取正，所有的利润取负，如果当前利润为正，表示已经亏本，停止增广。建立源点，向每个月份建边，容量为mi,边权为ni；每个月向汇点建边，容量为si,边权为-pi;每个月份i向所能保存到的月份j建边，容量为INF，边权为I*（j-i）.
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int maxn = 510; 8 const int maxe = (maxn + maxn + maxn*maxn) * 2 + 10; 9 const int INF = 0x3f3f3f3f; 10 struct edge 11 { 12 int from, to, cap, flow, cost, next; 13 edge(int ff=0,int tt=0,int cc=0,int ww=0,int ss=0,int nn=0):from(ff),to(tt),cap(cc),flow(ww),cost(ss),next(nn){ } 14 }Edge[maxe]; 15 int Head[maxn], totedge; 16 17 struct MCMF 18 { 19 int pre[maxn];//记录在增广路径上，到达i的边的编号 20 int dist[maxn]; 21 bool vis[maxn]; 22 int N,st,ed; 23 24 void Init() 25 { 26 memset(Head, -1, sizeof(Head)); 27 totedge = 0; 28 } 29 30 void Set(int nodes, int source, int dest) 31 { 32 N = nodes, st = source, ed = dest; 33 } 34 35 void addedge(int from, int to, int cap, int cost) 36 { 37 Edge[totedge] = edge(from, to, cap, 0, cost, Head[from]); 38 Head[from] = totedge++; 39 Edge[totedge] = edge(to, from, 0, 0, -cost, Head[to]); 40 Head[to] = totedge++; 41 } 42 43 bool SPFA(int s, int t)//跑一遍SPFA 找s——t的最少花销路径 且该路径上每一条边不能满流 ,若存在 说明可以继续增广，反之不能 44 { 45 queue q; 46 memset(dist, INF , sizeof(dist)); 47 memset(vis, 0, sizeof(vis)); 48 memset(pre, -1, sizeof(pre)); 49 50 dist[s] = 0; 51 vis[s] = true; 52 q.push(s); 53 while (!q.empty()) 54 { 55 int u = q.front(); 56 q.pop(); 57 vis[u] = false; 58 59 for (int i = Head[u]; i != -1; i = Edge[i].next) 60 { 61 if (dist[Edge[i].to] > dist[u] + Edge[i].cost&&Edge[i].cap > Edge[i].flow) 62 { 63 dist[Edge[i].to] = dist[u] + Edge[i].cost; 64 pre[Edge[i].to] = i; 65 if (!vis[Edge[i].to]) 66 { 67 vis[Edge[i].to] = true; 68 q.push(Edge[i].to); 69 } 70 } 71 } 72 } 73 return pre[t] != -1&&dist[t]<=0; 74 } 75 76 void cal_MCMF(long long&cost,long long&flow) 77 { 78 flow = 0, cost = 0; 79 while (SPFA(st, ed)) 80 { 81 //通过反向弧,在源点到汇点的最少花费路径 找最小增广流 82 int Min = INF; 83 for (int i = pre[ed]; i != -1; i = pre[Edge[i ^ 1].to]) 84 { 85 Min = min(Min, Edge[i].cap - Edge[i].flow); 86 } 87 //增广 88 for (int i = pre[ed]; i != -1; i = pre[Edge[i ^ 1].to]) 89 { 90 Edge[i].flow += Min; 91 Edge[i ^ 1].flow -= Min; 92 cost +=1ll*Edge[i].cost*Min; 93 } 94 flow += Min; 95 } 96 } 97 }mcmf; 98 99 int M, I;//总月份，每保存一个月的花费100 struct node101 {102 int mi, ni, pi, si, Ei;//单位生产费用；最大生产量；单位销售价格；最大销售量限制；可保存月份103 node(int mm=0,int nn=0,int pp=0,int ss=0,int ee=0):mi(mm),ni(nn),pi(pp),si(ss),Ei(ee){ }104 }parameters[110];105 int main()106 {107 int t;108 scanf("%d", &t);109 int Case = 1;110 while (t--)111 {112 scanf("%d%d", &M, &I);113 for (int i = 1; i <= M; i++)114 {115 scanf("%d%d%d%d%d", ¶meters[i].mi, ¶meters[i].ni, ¶meters[i].pi, ¶meters[i].si, ¶meters[i].Ei);116 }117 mcmf.Init();118 mcmf.Set(2 * M + 2, 0, 2 * M + 1);119 for (int i = 1; i <= M; i++)120 {121 mcmf.addedge(0, 2 * i - 1, parameters[i].ni, parameters[i].mi);//本题求最大利润，费用+122 mcmf.addedge(2 * i, 2 * M + 1, parameters[i].si,-parameters[i].pi);//本题求最大利润，卖出-123 }124 for (int i = 1; i <= M; i++)125 {126 for (int j = i; j <= min(i + parameters[i].Ei, M); j++)127 {128 mcmf.addedge(2 * i - 1, 2 * j, INF, I*(j - i));//I*(j - i)表示每单位从i月保存至j月需要的费用129 }130 }131 long long flow, cost;132 mcmf.cal_MCMF(cost, flow);133 printf("Case %d: %lld\n", Case++, -cost);134 }135 return 0;136 }
3、uva 10806 Dijkstra, Dijkstra
题意：有n个结点，监狱在1，车站在n,一共有m条无向边，每条边有一个边权表示走这条的时间花费，每条边只能走一次。现在有两个人要从监狱逃出，求能否达到车站，且时间最短？
思路：设一个源点，到监狱1建边，容量为2，花费为0；每条无向边拆成两条有向边，容量为1，边权为时间花费。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int maxn = 110; 8 const int maxe = maxn*maxn*4+10; 9 const int INF = 0x3f3f3f3f; 10 struct edge 11 { 12 int from, to, cap, flow, cost, next; 13 edge(int ff = 0, int tt = 0, int cc = 0, int ww = 0, int ss = 0, int nn = 0) :from(ff), to(tt), cap(cc), flow(ww), cost(ss), next(nn){ } 14 }Edge[maxe]; 15 int Head[maxn], totedge; 16 17 struct MCMF 18 { 19 int pre[maxn]; 20 int dist[maxn]; 21 bool vis[maxn]; 22 int N, st, ed; 23 24 void Init() 25 { 26 memset(Head, -1, sizeof(Head)); 27 totedge = 0; 28 } 29 30 void set(int nodes, int source, int dest) 31 { 32 N = nodes, st = source, ed = dest; 33 } 34 35 void addedge(int from, int to, int cap, int cost) 36 { 37 Edge[totedge] = edge(from, to, cap, 0, cost, Head[from]); 38 Head[from] = totedge++; 39 Edge[totedge] = edge(to, from, 0, 0, -cost, Head[to]); 40 Head[to] = totedge++; 41 } 42 43 bool SPFA() 44 { 45 queue q; 46 memset(dist, INF, sizeof(dist)); 47 memset(vis, 0, sizeof(vis)); 48 memset(pre, -1, sizeof(pre)); 49 50 dist[st] = 0; 51 vis[st] = true; 52 q.push(st); 53 while (!q.empty()) 54 { 55 int u = q.front(); 56 q.pop(); 57 vis[u] = false; 58 59 for (int i = Head[u]; i != -1; i = Edge[i].next) 60 { 61 if (dist[Edge[i].to] > dist[u] + Edge[i].cost&&Edge[i].cap > Edge[i].flow) 62 { 63 dist[Edge[i].to] = dist[u] + Edge[i].cost; 64 pre[Edge[i].to] = i; 65 if (!vis[Edge[i].to]) 66 { 67 vis[Edge[i].to] = true; 68 q.push(Edge[i].to); 69 } 70 } 71 } 72 } 73 return pre[ed] != -1; 74 } 75 76 void cal_MCMF(int &cost, int &flow) 77 { 78 flow = 0, cost = 0; 79 while (SPFA()) 80 { 81 int Min = INF; 82 for (int i = pre[ed]; i != -1; i = pre[Edge[i ^ 1].to]) 83 { 84 Min = min(Min, Edge[i].cap - Edge[i].flow); 85 } 86 for (int i = pre[ed]; i != -1; i = pre[Edge[i ^ 1].to]) 87 { 88 Edge[i].flow += Min; 89 Edge[i ^ 1].flow -= Min; 90 cost += Edge[i].cost*Min; 91 } 92 flow += Min; 93 } 94 } 95 }mcmf; 96 97 int n, m; 98 int main() 99 {100 while (~scanf("%d", &n) && n)101 {102 scanf("%d", &m);103 mcmf.Init();104 mcmf.set(n + 1, 0, n);105 mcmf.addedge(0, 1, 2, 0);106 for (int i = 1; i <= m; i++)107 {108 int u, v, c;109 scanf("%d%d%d", &u, &v, &c);110 mcmf.addedge(u, v, 1, c);111 mcmf.addedge(v, u, 1, c);112 }113 int cost, flow;114 mcmf.cal_MCMF(cost, flow);115 if (flow == 2) printf("%d\n", cost);116 else printf("Back to jail\n");117 }118 return 0;119 }