注意到题中是所有牛中最高选择的等级和所有牛中最低等级之差最小
就可以想到枚举区间长度 然后 枚举起点 来进行最大流了
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 1111
#define MAXM 55555
#define INF 10000007
using namespace std;
struct node
{
int v; // vtex
int c; // cacity
int f; // current f in this arc
int next, r;
}edge[MAXM];
int dist[MAXN], nm[MAXN], src, des, n;
int head[MAXN], e;
void add(int x, int y, int c)
{
edge[e].v = y;
edge[e].c = c;
edge[e].f = 0;
edge[e].r = e + 1;
edge[e].next = head[x];
head[x] = e++;
edge[e].v = x;
edge[e].c = 0;
edge[e].f = 0;
edge[e].r = e - 1;
edge[e].next = head[y];
head[y] = e++;
}
void rev_BFS()
{
int Q[MAXN], h = 0, t = 0;
for(int i = 1; i <= n; ++i)
{
dist[i] = MAXN;
nm[i] = 0;
}
Q[t++] = des;
dist[des] = 0;
nm[0] = 1;
while(h != t)
{
int v = Q[h++];
for(int i = head[v]; i != -1; i = edge[i].next)
{
if(edge[edge[i].r].c == 0 || dist[edge[i].v] < MAXN)continue;
dist[edge[i].v] = dist[v] + 1;
++nm[dist[edge[i].v]];
Q[t++] = edge[i].v;
}
}
}
void init()
{
e = 0;
memset(head, -1, sizeof(head));
}
int maxflow()
{
rev_BFS();
int u;
int total = 0;
int cur[MAXN], rpath[MAXN];
for(int i = 1; i <= n; ++i)cur[i] = head[i];
u = src;
while(dist[src] < n)
{
if(u == des) // find an augmenting path
{
int tf = INF;
for(int i = src; i != des; i = edge[cur[i]].v)
tf = min(tf, edge[cur[i]].c);
for(int i = src; i != des; i = edge[cur[i]].v)
{
edge[cur[i]].c -= tf;
edge[edge[cur[i]].r].c += tf;
edge[cur[i]].f += tf;
edge[edge[cur[i]].r].f -= tf;
}
total += tf;
u = src;
}
int i;
for(i = cur[u]; i != -1; i = edge[i].next)
if(edge[i].c > 0 && dist[u] == dist[edge[i].v] + 1)break;
if(i != -1) // find an admissible arc, then Advance
{
cur[u] = i;
rpath[edge[i].v] = edge[i].r;
u = edge[i].v;
}
else // no admissible arc, then relabel this vtex
{
if(0 == (--nm[dist[u]]))break; // GAP cut, Important!
cur[u] = head[u];
int mindist = n;
for(int j = head[u]; j != -1; j = edge[j].next)
if(edge[j].c > 0)mindist = min(mindist, dist[edge[j].v]);
dist[u] = mindist + 1;
++nm[dist[u]];
if(u != src)
u = edge[rpath[u]].v; // Backtrack
}
}
return total;
}
int nt, b;
int val[MAXN][33];
int cc[33];
bool solve(int mid)
{
src = nt + b + 1;
des = nt + b + 2;
n = des;
for(int k = 1; k <= b - mid + 1; k++)
{
init();
for(int i = 1; i <= nt; i++) add(src, i, 1);
for(int i = 1; i <= b; i++) add(nt + i, des, cc[i]);
for(int i = 1; i <= nt; i++)
for(int j = k; j < k + mid; j++)
add(i, val[i][j] + nt, 1);
if(maxflow() == nt) return true;
}
return false;
}
int main()
{
scanf("%d%d", &nt, &b);
for(int i = 1; i <= nt; i++)
for(int j = 1; j <= b; j++)
scanf("%d", &val[i][j]);
for(int i = 1; i <= b; i++) scanf("%d", &cc[i]);
int low = 1, high = b;
int ans = b;
while(low <= high)
{
int mid = (low + high) >> 1;
if(solve(mid))
{
ans = min(ans, mid);
high = mid - 1;
}
else low = mid + 1;
}
printf("%d\n", ans);
return 0;
}
分享到:
相关推荐
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
该题记录了本人研究该题的记录,有些是心得,希望能给大家帮助。
poj2516代码最小费用最大流
poj 800+ 题目源代码,多年做题积累 包含各种类型经典题目
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
西北工业大学POJ试题C++答案代码+课程设计
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
很好很强大的POJ分类 新手+进阶+题目完全分类 赶快下载
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ2195-Going Home【费用流】 解题报告+AC代码 http://blog.csdn.net/lyy289065406/article/details/6732762
北大POJ1159-Palindrome 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1750462
poj openjudge 1111题最大正向匹配 提交ac
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
POJ1837-Balance 解题报告+AC代码