如题,我这题的思路和题解一样,都是把人放在中间拆成两个点,dinic代码也过了模板,但是样例都跑不过 死循环
#include <stdio.h>
#include <vector>
#include <queue>
#define MAXN 500
using namespace std;
struct edge
{
int u,v,w;
edge()
{
}
edge(int from,int to,int weight)
{
u = from,v = to,w = weight;
}
};
vector<int> G[MAXN];
vector<edge> E;
int s,t;
int n,p,q;
void AddEdge(int u,int v,int w)
{
E.push_back(edge(u,v,w));
E.push_back(edge(v,u,0));
G[u].push_back(E.size() - 2);
G[v].push_back(E.size() - 1);
}
int cur[MAXN],dep[MAXN],inq[MAXN];
queue<int> bq;
bool bfs()
{
for(int i = 0; i <= n; i++)
{
cur[i] = 0,dep[i] = 0,inq[i] = 0;
}
inq[s] = 1;
dep[s] = 1;
bq.push(s);
while(!bq.empty())
{
int u = bq.front();
bq.pop();
for(int i = 0; i < G[u].size(); i++)
{
edge & e = E[G[u][i]];
if(!inq[e.v] && e.w)
{
inq[e.v] = 1;
dep[e.v] = dep[u] + 1;
bq.push(e.v);
}
}
}
if(inq[t])
return 1;
return 0;
}
int maxFlow;
int dfs(int u,int flow)
{
if(u == t)
{
maxFlow += flow;
return flow;
}
int used = 0,rlow = 0;
for(int i = cur[u]; i < G[u].size(); i++)
{
cur[u] = i;
edge & e = E[G[u][i]];
edge & re = E[G[u][i] ^ 1];
if(e.w && dep[e.v] == dep[u] + 1)
{
if(rlow = dfs(e.v,min(flow - used,e.w)))
{
used += rlow;
e.w -= rlow,re.w += rlow;
if(used == flow)
break;
}
}
}
return used;
}
int dinic()
{
while(bfs())
{
dfs(s,2147483647);
}
return maxFlow;
}
//第n位客人的节点编号 第n位的右边的一个点是cus[n + 1]
int cus[MAXN];
int dish[MAXN],room[MAXN];
int nnt = 1;//nodeCnt
int main(void)
{
scanf("%d%d%d",&n,&p,&q);
for(int i = 1; i <= n; i++)
{
cus[i] = nnt;
AddEdge(nnt,nnt + 1,1);
nnt += 2;
}
for(int i = 1; i <= p; i++)
{
room[i] = nnt;
nnt++;
}
for(int i = 1; i <= q; i++)
{
dish[i] = nnt;
nnt++;
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= p; j++)
{
int x;
scanf("%d",&x);
if(x == 1)
{
AddEdge(room[j],cus[i],1);
}
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= q; j++)
{
int x;
scanf("%d",&x);
if(x == 1)
{
AddEdge(cus[i] + 1,dish[j],1);
}
}
}
s = nnt;
nnt++;
t = nnt;
nnt++;
for(int i = 1; i <= p; i++)
{
AddEdge(s,room[i],1);
}
for(int i = 1; i <= q; i++)
{
AddEdge(dish[i],t,1);
}
printf("%d",dinic());
}