POJ2669不错的最大流 竞赛问题（枚举King的个数）
题意：
有n个人，任意两个人都比一次赛（一共比了n*(n-1)/2场），赢一场得到一分，最后的时候如果得分最高，或者是自己打败了所有比自己得分都高的人就算是King,给你每个人的最后得分，问最多有多少个人是King.
思路：
一开始上了就贪心了一次，WA了，改了改之后又贪心了一次，还是没过，然后换思路（其实做这个题目是本着最大流来的），然后就去考虑最大流，最大流的话也比较容易理解，关键是枚举的时候有点说道，先说下建图，把每个人看成一个点，然后把每场比赛看成一个点，源点连接所有人，流量为得分，所有比赛连接汇点，流量1，说到这估计大多数都能建图了吧，接着说，然后就是对于那些King的点，如果和他相关的比赛节点中的另一个点比他分高，那么他一定要赢这场比赛，那么他连接这场比赛的点，否则的话就是不确定，谁赢都行，那么和这场比赛相关的两个点都连接这场比赛就行了，最多11个人左右吧，那么可以直接枚举谁是King,最保守而且没争议的方法就是暴力搜索枚举，就是01枚举，2^10*最大流时间，这个完全可以接受，然后就是网上说的那种直接枚举个数的说法，这个说法要明确一个问题，那就是如果当前有m个King,那么这m个不一定必须是后m个，也可以是中间的一些个，但是按照结论反推可以知道，这m个可以是后m个，也就是说即使不是后m个也可以转换成后m个，所以直接枚举后m就行，关键是要明白不是后m个是怎么可以转换成后m个的，我的想法一开始是找两个点，假设1..i..j..n,假如i是King,而j不是，那么就想办法吧ij的关系调换，就是让i变成不是King,而j是King,按照结论反推肯定是可以调换的，但是我想了很多方法都没有平衡掉ij之间的数字，找网上的也没有可以让我信服的，但是我自己有一个猜想，那就是我感觉可以按照贪心的方式去理解，越往后的称为King的代价就越小，也就是消耗的总的固定流量就越小，那么当然是越往后越可能了，枚举当然那是从后面开始，还有一个问题就是我感觉如果当前序列有k个可以称为King的话，那么一定可以转换成后k个，但是如果当前是后k个的话，不一定能往前转换，也就是我感觉后k个是最优的选择，就是类似那种后k个可以，但是还余出来一些资源没用，通过这些资源可以吧后k个中的一些挪到前面来，这样就产生了答案不以为的情况，但是直接枚举后k个是最优的方式，所有是正确的，这个也只是自己的感觉而已，已过想证明必须要把得分平衡掉。。。。下面是两种方法的代码，我的流用的是DINIC，估计姿势不优吧，速度和网上别人的速度比慢了很多.
DFS+DINIC
#include<queue>
#include<stdio.h>
#include<string.h>
#define N_node 150
#define N_edge 5000
#define INF 1000000000
using namespace std;
typedef struct
{
int to ,cost ,next;
}STAR;
typedef struct
{
int x ,t;
}DEP;
STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,listt[N_node] ,tot;
int deep[N_node];
void add(int a ,int b ,int c)
{
E[++tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;
E[++tot].to = a;
E[tot].cost = 0;
E[tot].next = list[b];
list[b] = tot;
}
int minn(int x ,int y)
{
return x < y ? x : y;
}
bool BFS_DEEP(int s ,int t ,int n)
{
memset(deep ,255 ,sizeof(deep));
xin.x = s ,xin.t = 0;
queue<DEP>q;
q.push(xin);
deep[s] = 0;
while(!q.empty())
{
tou = q.front();
q.pop();
for(int k = list[tou.x] ;k ;k = E[k].next)
{
xin.x = E[k].to;
xin.t = tou.t + 1;
if(deep[xin.x] != -1 || !E[k].cost)
continue;
deep[xin.x] = xin.t;
q.push(xin);
}
}
for(int i = 0 ;i <= n ;i ++)
listt[i] = list[i];
return deep[t] != -1;
}
int DFS_Flow(int s ,int t ,int flow)
{
if(s == t) return flow;
int nowflow = 0;
for(int k = listt[s] ;k ;k = E[k].next)
{
listt[s] = k;
int c = E[k].cost;
int to = E[k].to;
if(!c || deep[to] != deep[s] + 1)
continue;
int tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));
nowflow += tmp;
E[k].cost -= tmp;
E[k^1].cost += tmp;
if(nowflow == flow) break;
}
if(!nowflow) deep[s] = 0;
return nowflow;
}
int DINIC(int s ,int t ,int n)
{
int ans = 0;
while(BFS_DEEP(s ,t ,n))
{
ans += DFS_Flow(s ,t ,INF);
}
return ans;
}
int now[15] ,num[15];
int Ans ,maxn ,n;
void Flow()
{
memset(list ,0 ,sizeof(list));
tot = 1;
for(int i = 1 ;i <= n ;i ++)
add(0 ,i ,num[i]);
int nowid = n;
for(int i = 1 ;i <= n ;i ++)
for(int j = i + 1 ;j <= n ;j ++)
{
++nowid;
if(num[i] < num[j] && now[i])
add(i ,nowid ,1);
else if(num[j] < num[i] && now[j])
add(j ,nowid ,1);
else add(i ,nowid ,1) ,add(j ,nowid ,1);
add(nowid ,n + n * (n - 1) / 2 + 1 ,1);
}
int flow = DINIC(0 ,n + n * (n - 1) / 2 + 1 ,n + n * (n - 1) / 2 + 1);
if(flow == n * (n - 1) / 2)
{
int s = 0;
for(int i = 1 ;i <= n ;i ++)
s += now[i];
if(Ans < s) Ans = s;
}
return ;
}
void DFS(int nowid)
{
if(nowid == maxn + 1)
{
Flow();
return;
}
now[nowid] = 0;
DFS(nowid + 1);
now[nowid] = 1;
DFS(nowid + 1);
}
int main ()
{
int t ,i ,nowid;
char str[30];
scanf("%d" ,&t);
getchar();
while(t--)
{
gets(str);
int len = strlen(str);
nowid = 0;
for(i = 0 ;i < len ;i ++)
{
if(str[i] >= '0' && str[i] <= '9')
{
if(i == len - 1 || str[i+1] < '0' || str[i+1] > '9')
num[++nowid] = str[i] - '0';
else
{
num[++nowid] = (str[i] - '0') * 10 + str[i+1] - '0';
i ++;
}
}
}
n = nowid;
for(i = n ;i >= 1 ;i --)
{
if(num[i] == num[n])
{
maxn = i;
now[i] = 1;
}
else now[i] = 0;
}
if(maxn == 1)
{
printf("%d\n" ,n);
continue;
}
Ans = 0;
DFS(1);
printf("%d\n" ,Ans);
}
return 0;
}
枚举后几位+DINIC
#include<queue>
#include<stdio.h>
#include<string.h>
#define N_node 150
#define N_edge 5000
#define INF 1000000000
using namespace std;
typedef struct
{
int to ,cost ,next;
}STAR;
typedef struct
{
int x ,t;
}DEP;
STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,listt[N_node] ,tot;
int deep[N_node];
int num[15];
void add(int a ,int b ,int c)
{
E[++tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;
E[++tot].to = a;
E[tot].cost = 0;
E[tot].next = list[b];
list[b] = tot;
}
int minn(int x ,int y)
{
return x < y ? x : y;
}
bool BFS_DEEP(int s ,int t ,int n)
{
memset(deep ,255 ,sizeof(deep));
xin.x = s ,xin.t = 0;
queue<DEP>q;
q.push(xin);
deep[s] = 0;
while(!q.empty())
{
tou = q.front();
q.pop();
for(int k = list[tou.x] ;k ;k = E[k].next)
{
xin.x = E[k].to;
xin.t = tou.t + 1;
if(deep[xin.x] != -1 || !E[k].cost)
continue;
deep[xin.x] = xin.t;
q.push(xin);
}
}
for(int i = 0 ;i <= n ;i ++)
listt[i] = list[i];
return deep[t] != -1;
}
int DFS_Flow(int s ,int t ,int flow)
{
if(s == t) return flow;
int nowflow = 0;
for(int k = listt[s] ;k ;k = E[k].next)
{
listt[s] = k;
int c = E[k].cost;
int to = E[k].to;
if(!c || deep[to] != deep[s] + 1)
continue;
int tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));
nowflow += tmp;
E[k].cost -= tmp;
E[k^1].cost += tmp;
if(nowflow == flow) break;
}
if(!nowflow) deep[s] = 0;
return nowflow;
}
int DINIC(int s ,int t ,int n)
{
int ans = 0;
while(BFS_DEEP(s ,t ,n))
{
ans += DFS_Flow(s ,t ,INF);
}
return ans;
}
int Flow(int now ,int n)
{
memset(list ,0 ,sizeof(list));
tot = 1;
int s = 0 ,t = n + n * (n - 1) / 2 + 1;
for(int i = 1 ;i <= n ;i ++)
add(s ,i ,num[i]);
int nowid = n;
for(int i = 1 ;i <= n ;i ++)
for(int j = i + 1 ;j <= n ;j ++)
{
++nowid;
if(num[i] < num[j] && i >= now)
add(i ,nowid ,1);
else if(num[j] < num[i] && j >= now)
add(j ,nowid ,1);
else add(i ,nowid ,1) ,add(j ,nowid ,1);
add(nowid ,t ,1);
}
return DINIC(s ,t ,t);
}
int main ()
{
int i ,nowid ,t;
char str[30];
scanf("%d" ,&t);
getchar();
while(t--)
{
gets(str);
int len = strlen(str);
nowid = 0;
for(i = 0 ;i < len ;i ++)
{
if(str[i] >= '0' && str[i] <= '9')
{
if(i == len - 1 || str[i+1] < '0' || str[i + 1] > '9')
num[++nowid] = str[i] - '0';
else
{
num[++nowid] = (str[i] - '0') * 10 + str[i+1] - '0';
i ++;
}
}
}
int list;
for(i = nowid ;i >= 1 ;i --)
if(num[i] == num[nowid]) list = i;
if(list == 1)
{
printf("%d\n" ,nowid);
continue;
}
for(i = 1 ;i <= nowid ;i ++)
{
if(Flow(i ,nowid) == nowid * (nowid - 1) / 2)
break;
}
printf("%d\n" ,nowid - i + 1);
}
return 0;
}
最新文章
- Java怎么导入一个项目？
- JS函数节流
- Redis批量删除KEY的方法
- [Objective-C 面试简要笔记]
- 第二篇：SOUI源码的获取及编译
- storm-kafka-0.8-plus 源码解析
- js取配置文件内容
- JAVA坏境变量中的JAVA_HOME path classpath 的设置与作用。
- 提高Linux安全性--hosts.allow, hosts.deny 文件修改方法
- Android基于GridView实现的翻牌游戏效果
- 用sp_addlinkedserver建立链接服务器（sql server2008中通过测试）
- VB学习笔记
- java多线程编程（3）买票
- rabbitmq重装之后无法加入原有cluster的bug解析
- Spring Boot 快速入门笔记
- php+redis 实现消息队列的推送【demo】。
- nvm 查看node版本
- MFC原理第一讲.MFC的本质.以及手工编写MFC的程序
- 聊聊找AI算法岗工作
- Shell编程（八）每隔N分钟执行某脚本