題意：
? ? ? 有一n個(gè)冰塊，每個(gè)冰塊上都有一些企鵝，所有的企鵝要跳到一個(gè)冰塊上去，但是由于起跳是的后坐力原因?qū)е旅總€(gè)冰塊最多條mi次，最后問(wèn)你所有的企鵝都跳到一個(gè)冰塊上去的那塊冰塊可以是哪一塊，輸出所有肯能的終點(diǎn)冰塊。


思路：
? ? ? 比較簡(jiǎn)單，我們可以枚舉終點(diǎn)，首先把終點(diǎn)拿出來(lái)，剩下的點(diǎn)拆點(diǎn)，拆成兩個(gè)，限流是最多的跳躍次數(shù)，然后起點(diǎn)連接每個(gè)拆了的點(diǎn)的左側(cè)的點(diǎn)，終點(diǎn)就是當(dāng)前枚舉的點(diǎn)，然后最大流判斷下就行了，提醒下，建圖的時(shí)候注意，不要多虛擬出來(lái)一些沒(méi)用的點(diǎn)，一開(kāi)始我的第一感覺(jué)就是三重的，后來(lái)在敲的時(shí)候突然感覺(jué)兩重就夠了，也就是最多200個(gè)點(diǎn)就行，還有就是當(dāng)前枚舉的重點(diǎn)的冰塊上的企鵝不用動(dòng)，別的沒(méi)什么，因?yàn)楸容^簡(jiǎn)單，我就不解釋太多了，不清楚的自己畫(huà)畫(huà)建出來(lái)的圖應(yīng)該很容易懂。


#include<queue>
#include<stdio.h>
#include<string.h>


#define N_node 200 + 10
#define N_edge 100000
#define INF 1000000000


using namespace std;


typedef struct
{
? ? int to ,cost ,next;
}STAR;


typedef struct
{
? ? int x ,t;
}DEP;


typedef struct
{
? ? double x ,y;
? ? int p ,c;
}NODE;


NODE node[N_node];
STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,listt[N_node] ,tot;
int deep[N_node] ,Ans[N_node];
int canlink[110][110];


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


double Get_Dis(NODE a ,NODE b)
{
? ? double x = (a.x - b.x) * (a.x - b.x);
? ? double y = (a.y - b.y) * (a.y - b.y);
? ? return x + y;
}


int main ()
{
? ? int t ,n ,i ,j ,sump;
? ? double dis;
? ? scanf("%d" ,&t);
? ? while(t--)
? ? {
? ? ? ? scanf("%d %lf" ,&n ,&dis);
? ? ? ? sump = 0;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%lf %lf %d %d" ,&node[i].x ,&node[i].y ,&node[i].p ,&node[i].c);
? ? ? ? ? ? sump += node[i].p;
? ? ? ? }
? ? ? ? memset(canlink ,0 ,sizeof(canlink));
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? for(j = i + 1 ;j <= n ;j ++)
? ? ? ? {
? ? ? ? ? ? if(Get_Dis(node[i] ,node[j]) <= dis * dis)
? ? ? ? ? ? canlink[i][j] = canlink[j][i] = 1;
? ? ? ? }
? ? ? ? int ansid = 0;
? ? ? ? for(int now = 1 ;now <= n ;now ++)
? ? ? ? {
? ? ? ? ? ? memset(list ,0 ,sizeof(list));
? ? ? ? ? ? tot = 1;
? ? ? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(i == now) continue;
? ? ? ? ? ? ? ? add(0 ,i ,node[i].p);
? ? ? ? ? ? ? ? add(i ,i + n ,node[i].c);
? ? ? ? ? ? }
? ? ? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? ? ? for(j = i + 1 ;j <= n ;j ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(canlink[i][j])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if(i == now) add(j + n ,now ,INF);
? ? ? ? ? ? ? ? ? ? else if(j == now) add(i + n ,now ,INF);
? ? ? ? ? ? ? ? ? ? else add(i + n ,j ,INF) ,add(j + n ,i ,INF);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? int flow = DINIC(0 ,now ,n + n);
? ? ? ? ? ? if(flow == sump - node[now].p)
? ? ? ? ? ? Ans[++ansid] = now;
? ? ? ? }
? ? ? ? if(!ansid) printf("-1\n");
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? for(i = 1 ;i <= ansid ;i ++)
? ? ? ? ? ? if(i == ansid) printf("%d\n" ,Ans[i] - 1);
? ? ? ? ? ? else printf("%d " ,Ans[i] - 1);
? ? ? ? }
? ? }
? ? return 0;
}

總結(jié)

以上是生活随笔為你收集整理的POJ3498最大流，枚举终点，企鹅，基础最大流的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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