題意：
? ? ? 有n個(gè)人，任意兩個(gè)人都比一次賽（一共比了n*(n-1)/2場），贏一場得到一分，最后的時(shí)候如果得分最高，或者是自己打敗了所有比自己得分都高的人就算是King,給你每個(gè)人的最后得分，問最多有多少個(gè)人是King.


思路：
? ? ? 一開始上了就貪心了一次，WA了，改了改之后又貪心了一次，還是沒過，然后換思路（其實(shí)做這個(gè)題目是本著最大流來的），然后就去考慮最大流，最大流的話也比較容易理解，關(guān)鍵是枚舉的時(shí)候有點(diǎn)說道，先說下建圖，把每個(gè)人看成一個(gè)點(diǎn)，然后把每場比賽看成一個(gè)點(diǎn)，源點(diǎn)連接所有人，流量為得分，所有比賽連接匯點(diǎn)，流量1，說到這估計(jì)大多數(shù)都能建圖了吧，接著說，然后就是對于那些King的點(diǎn)，如果和他相關(guān)的比賽節(jié)點(diǎn)中的另一個(gè)點(diǎn)比他分高，那么他一定要贏這場比賽，那么他連接這場比賽的點(diǎn)，否則的話就是不確定，誰贏都行，那么和這場比賽相關(guān)的兩個(gè)點(diǎn)都連接這場比賽就行了，最多11個(gè)人左右吧，那么可以直接枚舉誰是King,最保守而且沒爭議的方法就是暴力搜索枚舉，就是01枚舉，2^10*最大流時(shí)間，這個(gè)完全可以接受，然后就是網(wǎng)上說的那種直接枚舉個(gè)數(shù)的說法，這個(gè)說法要明確一個(gè)問題，那就是如果當(dāng)前有m個(gè)King,那么這m個(gè)不一定必須是后m個(gè)，也可以是中間的一些個(gè)，但是按照結(jié)論反推可以知道，這m個(gè)可以是后m個(gè)，也就是說即使不是后m個(gè)也可以轉(zhuǎn)換成后m個(gè)，所以直接枚舉后m就行，關(guān)鍵是要明白不是后m個(gè)是怎么可以轉(zhuǎn)換成后m個(gè)的，我的想法一開始是找兩個(gè)點(diǎn)，假設(shè)1..i..j..n,假如i是King,而j不是，那么就想辦法吧ij的關(guān)系調(diào)換，就是讓i變成不是King,而j是King,按照結(jié)論反推肯定是可以調(diào)換的，但是我想了很多方法都沒有平衡掉ij之間的數(shù)字，找網(wǎng)上的也沒有可以讓我信服的，但是我自己有一個(gè)猜想，那就是我感覺可以按照貪心的方式去理解，越往后的稱為King的代價(jià)就越小，也就是消耗的總的固定流量就越小，那么當(dāng)然是越往后越可能了，枚舉當(dāng)然那是從后面開始，還有一個(gè)問題就是我感覺如果當(dāng)前序列有k個(gè)可以稱為King的話，那么一定可以轉(zhuǎn)換成后k個(gè)，但是如果當(dāng)前是后k個(gè)的話，不一定能往前轉(zhuǎn)換，也就是我感覺后k個(gè)是最優(yōu)的選擇，就是類似那種后k個(gè)可以，但是還余出來一些資源沒用，通過這些資源可以吧后k個(gè)中的一些挪到前面來，這樣就產(chǎn)生了答案不以為的情況，但是直接枚舉后k個(gè)是最優(yōu)的方式，所有是正確的，這個(gè)也只是自己的感覺而已，已過想證明必須要把得分平衡掉。。。。下面是兩種方法的代碼，我的流用的是DINIC，估計(jì)姿勢不優(yōu)吧，速度和網(wǎng)上別人的速度比慢了很多.




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;
}

總結(jié)

以上是生活随笔為你收集整理的POJ2669不错的最大流 竞赛问题（枚举King的个数）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。