首页 > 代码库 > HDOJ 5383 Yu-Gi-Oh! 最大费用最大流
HDOJ 5383 Yu-Gi-Oh! 最大费用最大流
网络流裸题:
分两部分建图,求不要求满流的最大费用最大流.....
Yu-Gi-Oh!
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 401 Accepted Submission(s): 108
Problem Description
"Yu-Gi-Oh!", also known as "Dueling Monsters", is a popular trading card game which has nearly 20 years history. Next year, YGO will reach its 20th birthday.
Stilwell has monsters on the desk, each monster has its and . There are two kinds of monsters, Tuner monsters and Non-Tuner monsters.
Now, Stilwell plans to finish some "Synchro Summon", and "Synchro Summon" is a kind of special summon following these rules (a little different from the standard YGO rules):
(1) A "Synchro Summon" needs two monsters as the material of this summon, and they must be one Tuner monster and one Non-Tuner monster.
In other words, we can cost one Tuner monster and one Non-Tuner monster to get a Synchro monster ("cost" means remove form the desk, "get" means put on to the desk).
(2) To simplify this problem, Synchro monsters are neither Tuner monsters nor Non-Tuner monsters.
(3) The level sum of two material must be equal to the level of Synchro monster we summon.
For example:
A Level 3 Tuner monster A Level 2 Non-Tuner monster A Level 5 Synchro Monster
A Level 2 Tuner monster A Level 4 Non-Tuner monster A Level 6 Synchro Monster
A Level 4 Tuner monster A Level 4 Non-Tuner monster A Level 8 Synchro Monster
(4) The material of some Synchro monster has some limits, the material must contain some specific monster.
For example:
A Level 5 Synchro Monster requires A Level 3 Tuner monster to be its material
A Level 6 Synchro Monster requires A Level 4 Non-Tuner monster to be its material
A Level 8 Synchro Monster requires A Level 4 Tuner monster A Level 4 Non-Tuner monster to be its material
A Level 5 Synchro Monster doesn‘t require any monsters to be its material
Then
A Level 3 Tuner monster A Level 2 Non-Tuner monster A Level 5 Synchro Monster
A Level 3 Tuner monster A Level 2 Non-Tuner monster A Level 5 Synchro Monster
A Level 2 Tuner monster A Level 4 Non-Tuner monster A Level 6 Synchro Monster
A Level 3 Tuner monster A Level 3 Non-Tuner monster A Level 6 Synchro Monster
A Level 4 Tuner monster A Level 4 Non-Tuner monster A Level 8 Synchro Monster
A Level 4 Tuner monster A Level 4 Non-Tuner monster A Level 8 Synchro Monster
A Level 4 Tuner monster A Level 4 Non-Tuner monster A Level 8 Synchro Monster
A Level 3 Tuner monster A Level 2 Non-Tuner monster A Level 5 Synchro Monster
A Level 3 Tuner monster A Level 2 Non-Tuner monster A Level 5 Synchro Monster
Stilwell has kinds of Synchro Monster cards, the quantity of each Synchro Monster cards is infinity.
Now, given and of every card on desk and every kind of Synchro Monster cards. Please finish some Synchro Summons (maybe zero) to maximum of the cards on desk.
Stilwell has monsters on the desk, each monster has its and . There are two kinds of monsters, Tuner monsters and Non-Tuner monsters.
Now, Stilwell plans to finish some "Synchro Summon", and "Synchro Summon" is a kind of special summon following these rules (a little different from the standard YGO rules):
(1) A "Synchro Summon" needs two monsters as the material of this summon, and they must be one Tuner monster and one Non-Tuner monster.
In other words, we can cost one Tuner monster and one Non-Tuner monster to get a Synchro monster ("cost" means remove form the desk, "get" means put on to the desk).
(2) To simplify this problem, Synchro monsters are neither Tuner monsters nor Non-Tuner monsters.
(3) The level sum of two material must be equal to the level of Synchro monster we summon.
For example:
A Level 3 Tuner monster A Level 2 Non-Tuner monster A Level 5 Synchro Monster
A Level 2 Tuner monster A Level 4 Non-Tuner monster A Level 6 Synchro Monster
A Level 4 Tuner monster A Level 4 Non-Tuner monster A Level 8 Synchro Monster
(4) The material of some Synchro monster has some limits, the material must contain some specific monster.
For example:
A Level 5 Synchro Monster requires A Level 3 Tuner monster to be its material
A Level 6 Synchro Monster requires A Level 4 Non-Tuner monster to be its material
A Level 8 Synchro Monster requires A Level 4 Tuner monster A Level 4 Non-Tuner monster to be its material
A Level 5 Synchro Monster doesn‘t require any monsters to be its material
Then
A Level 3 Tuner monster A Level 2 Non-Tuner monster A Level 5 Synchro Monster
A Level 3 Tuner monster A Level 2 Non-Tuner monster A Level 5 Synchro Monster
A Level 2 Tuner monster A Level 4 Non-Tuner monster A Level 6 Synchro Monster
A Level 3 Tuner monster A Level 3 Non-Tuner monster A Level 6 Synchro Monster
A Level 4 Tuner monster A Level 4 Non-Tuner monster A Level 8 Synchro Monster
A Level 4 Tuner monster A Level 4 Non-Tuner monster A Level 8 Synchro Monster
A Level 4 Tuner monster A Level 4 Non-Tuner monster A Level 8 Synchro Monster
A Level 3 Tuner monster A Level 2 Non-Tuner monster A Level 5 Synchro Monster
A Level 3 Tuner monster A Level 2 Non-Tuner monster A Level 5 Synchro Monster
Stilwell has kinds of Synchro Monster cards, the quantity of each Synchro Monster cards is infinity.
Now, given and of every card on desk and every kind of Synchro Monster cards. Please finish some Synchro Summons (maybe zero) to maximum of the cards on desk.
Input
The first line of the input contains a single number ,
the number of test cases.
For each test case, the first line contains two integers , .
Next lines, each line contains three integers , , and , describe a monster on the desk. If this monster is a Tuner monster, then , else for Non-Tuner monster.
Next lines, each line contains integers , , , and following integers are the required material of this Synchro Monster (the integers given are the identifier of the required material).
The input data guarantees that the required material list is available, two Tuner monsters or two Non-Tuner monsters won‘t be required. If the level sum of two required material will be equal to the level of Synchro Monster.
, , , ,
For each test case, the first line contains two integers , .
Next lines, each line contains three integers , , and , describe a monster on the desk. If this monster is a Tuner monster, then , else for Non-Tuner monster.
Next lines, each line contains integers , , , and following integers are the required material of this Synchro Monster (the integers given are the identifier of the required material).
The input data guarantees that the required material list is available, two Tuner monsters or two Non-Tuner monsters won‘t be required. If the level sum of two required material will be equal to the level of Synchro Monster.
, , , ,
Output
lines,
find the maximum after
some Synchro Summons.
Sample Input
5 2 2 1 3 1300 0 2 900 5 2300 1 1 8 2500 0 2 1 1 3 1300 1 2 900 5 2300 1 1 3 1 1 3 1300 0 2 900 0 2 800 5 2300 1 1 3 1 1 1 233 0 1 233 0 1 200 2 466 2 1 2 6 3 1 3 1300 0 2 900 0 5 1350 1 4 1800 0 10 4000 0 10 1237 5 2300 1 1 8 3000 0 6 2800 0
Sample Output
2300 2200 3200 666 11037
Author
SXYZ
/* *********************************************** Author :CKboss Created Time :2015年08月17日 星期一 08时42分00秒 File Name :HDOJ5383.cpp ************************************************ */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <cmath> #include <cstdlib> #include <vector> #include <queue> #include <set> #include <map> using namespace std; const int INF=0x3f3f3f3f; const int maxv=400; const int maxn=maxv*maxv; struct Edge { int to,next,cap,flow,cost; }edge[maxn]; int n,m; int Adj[maxv],Size,N; void init() { memset(Adj,-1,sizeof(Adj)); Size=0; } void addedge(int u,int v,int cap,int cost) { edge[Size].to=v; edge[Size].next=Adj[u]; edge[Size].cost=cost; edge[Size].cap=cap; edge[Size].flow=0; Adj[u]=Size++; } void Add_Edge(int u,int v,int cap,int cost) { addedge(u,v,cap,cost); addedge(v,u,0,-cost); } int dist[maxv]; int vis[maxv],pre[maxv]; bool spfa(int s,int t) { queue<int> q; for(int i=0;i<N;i++) { dist[i]=-INF; vis[i]=false; pre[i]=-1; } dist[s]=0; vis[s]=true; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=false; for(int i=Adj[u];~i;i=edge[i].next) { int v=edge[i].to; if(edge[i].cap>edge[i].flow&& dist[v]<dist[u]+edge[i].cost) { dist[v]=dist[u]+edge[i].cost; pre[v]=i; if(!vis[v]) { vis[v]=true; q.push(v); } } } } if(pre[t]==-1) return false; return true; } int MinCostMaxFlow(int s,int t,int &cost) { int flow=0; cost=0; while(spfa(s,t)) { int Min=INF; for(int i=pre[t];~i;i=pre[edge[i^1].to]) { if(Min>edge[i].cap-edge[i].flow) Min=edge[i].cap-edge[i].flow; } if(dist[t]<0) break; for(int i=pre[t];~i;i=pre[edge[i^1].to]) { edge[i].flow+=Min; edge[i^1].flow-=Min; cost+=edge[i].cost*Min; } flow+=Min; } return flow; } struct Moster { Moster(){} Moster(int l,int a):level(l),ATK(a){} int level,ATK; }; vector<Moster> m0,m1; int turn[maxv],pos[maxv]; int GG[maxv][maxv]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int T_T; scanf("%d",&T_T); while(T_T--) { scanf("%d%d",&n,&m); init(); m0.clear(); m1.clear(); memset(GG,0,sizeof(GG)); int sumATK=0; int sz1=0,sz2=0; for(int i=0,t,l,a;i<n;i++) { scanf("%d%d%d",&t,&l,&a); if(t==0) { m0.push_back(Moster(l,a)); turn[i]=0; pos[i]=sz1++; } else if(t==1) { m1.push_back(Moster(l,a)); turn[i]=1; pos[i]=sz2++; } sumATK+=a; } for(int i=0,l,a,r;i<m;i++) { scanf("%d%d%d",&l,&a,&r); if(r==0) { for(int j=0;j<sz1;j++) { for(int k=0;k<sz2;k++) { int u=j+1,v=k+sz1+1; if(m0[j].level+m1[k].level==l) { if(a>m0[j].ATK+m1[k].ATK) { GG[u][v]=max(GG[u][v],a-m0[j].ATK-m1[k].ATK); } } } } } else if(r==1) { int x; scanf("%d",&x); x--; if(turn[x]==0) { int P=pos[x]; for(int j=0;j<sz2;j++) { int u=P+1,v=j+sz1+1; if(m0[P].level+m1[j].level==l) { if(a>m0[P].ATK+m1[j].ATK) { GG[u][v]=max(GG[u][v],a-m0[P].ATK-m1[j].ATK); } } } } else if(turn[x]==1) { int P=pos[x]; for(int j=0;j<sz1;j++) { int u=j+1,v=P+sz1+1; if(m0[j].level+m1[P].level==l) { if(a>m0[j].ATK+m1[P].ATK) { GG[u][v]=max(GG[u][v],a-m0[j].ATK-m1[P].ATK); } } } } } else if(r==2) { int x,y; scanf("%d%d",&x,&y); x--; y--; if(turn[x]==1) swap(x,y); int u=pos[x]+1,v=sz1+pos[y]+1; if(a>m0[pos[x]].ATK+m1[pos[y]].ATK) { GG[u][v]=max(GG[u][v],a-m0[pos[x]].ATK-m1[pos[y]].ATK); } } } for(int i=1;i<=sz1;i++) { for(int j=sz1+1;j<=sz1+sz2;j++) { if(GG[i][j]>0) Add_Edge(i,j,1,GG[i][j]); } } int S=0,T=sz1+sz2+1; for(int i=1;i<=sz1;i++) Add_Edge(0,i,1,0); for(int i=sz1+1;i<=sz1+sz2;i++) Add_Edge(i,T,1,0); int flow,cost; N=sz1+sz2+2; flow=MinCostMaxFlow(S,T,cost); printf("%d\n",sumATK+cost); } return 0; }
HDOJ 5383 Yu-Gi-Oh! 最大费用最大流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。