国庆八天乐，刷题也快乐。
HOJ崩了，但是VJ可以把题目挂出来。
题目链接：
涉及到矩阵里面的网络流，化为图来做。
某个点有流量限制，一定要想到拆点。
求最大值的话，要把w变成负数。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 const int maxn = 6e3; 9 const int INF = 1e9; 10 int vis[maxn],dist[maxn]; 11 int tot,head[maxn]; 12 int pv[maxn],pe[maxn]; 13 struct edge 14 { 15 int to,pre,cap,cost; 16 }e[100000]; 17 void init() 18 { 19 tot = 0; 20 memset(head,-1,sizeof(head)); 21 } 22 void add(int from,int to,int cap,int cost) 23 { 24 e[tot].pre = head[from]; 25 e[tot].to = to; 26 e[tot].cap = cap; 27 e[tot].cost = cost; 28 head[from] = tot++; 29 } 30 void addedge(int from,int to,int cap,int cost) 31 { 32 add(from,to,cap,cost); 33 add(to,from,0,-cost); 34 } 35 int n,k; 36 int min_cost_flow(int s,int t,int f,int& max_flow) 37 { 38 int ret = 0; 39 while(f>0&&(k--)) 40 { 41 memset(vis,0,sizeof(vis)); 42 for(int i=0;i
q; 45 q.push(s); 46 while(!q.empty()) 47 { 48 int v = q.front(); q.pop(); 49 vis[v] = 0; 50 for(int i=head[v];i>=0;i=e[i].pre) 51 { 52 int to = e[i].to,cap = e[i].cap,cost = e[i].cost; 53 if(cap>0&&dist[to]>dist[v]+cost) 54 { 55 pv[to] = v,pe[to] = i; 56 dist[to] = dist[v] + cost; 57 if(!vis[to]) q.push(to); 58 vis[to] = 1; 59 } 60 } 61 // printf("%d\n",v); 62 } 63 //printf("%d\n",dist[t]); 64 if(dist[t]==INF) return ret;///同一目的地，每次增广路都是最小费用 65 ///当所有边的流量都流净后，即没有残余网络，返回。 66 int d = f; 67 for(int v=t;v!=s;v=pv[v]) 68 { 69 d = min(d,e[pe[v]].cap); 70 } 71 f -= d; 72 max_flow += d; 73 ret += d*dist[t]; ///走一单位就消耗dist[t] 74 for(int v=t;v!=s;v=pv[v]) 75 { 76 e[pe[v]].cap -= d; 77 e[pe[v]^1].cap += d; 78 } 79 } 80 return ret; 81 } 82 int height[55][55]; 83 int value[55][55]; 84 int judge(int x,int y) 85 { 86 if(x<=0||x>=(n-1)||y<=0||y>=(n-1)) return 1; 87 else return 0; 88 } 89 int judge1(int x,int y) 90 { 91 if(x>=0&&x<=(n-1)&&y>=0&&y<=(n-1)) return 1; 92 else return 0; 93 } 94 int to[4][2] = { 1,0,-1,0,0,1,0,-1}; 95 int main() 96 { 97 int T;scanf("%d",&T); 98 while(T--) 99 {100 scanf("%d %d",&n,&k);101 init(); ///千万别忘记写102 for(int i=0;i
height[nextx][nexty])140 {141 addedge(i*n+j+n*n,nextx*n+nexty,INF,0);142 }143 }144 }145 }146 int max_flow = 0;147 int ans = min_cost_flow(s,t,INF,max_flow);148 if(ans==0)149 {150 printf("%d\n",ans);151 }152 else153 {154 printf("%d\n",-ans);155 }156 }157 return 0;158 }159 /*160 4 5161 1 2 1162 2 3 1163 3 4 1164 1 3 2165 2 4 1166 */