洛谷P2071座位安排
思路：
网络流难在建图上面。 这题（应该也可以，我没尝试过）用二分图匹配去跑。可以拆点，将一排的座位拆成两个点，一个
i
i
i,一个
i
+
n
i+n
i+n，然后匈牙利算法跑。 也可以用网络流跑最大流，将
S
S
S向每个人
i
i
i连一条流量为
1
1
1的边，再将每个人向他想坐的位置连一条流量为
1
1
1的边，至于每排座位可以坐两个人，可以将每排座位向
T
T
T连一条流量为
2
2
2的边，这样就可以让他的最大流量是
2
2
2了。
代码：
#include<bits/stdc++.h>
#define pii pair<int,int>
#define int long long
#define cl(x,y) memset(x,y,sizeof(x))
#define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
const int N
=5e5+210;
const int mod
=1e9+7;
const int maxn
=0x3f3f3f3f;
const int minn
=0xc0c0c0c0;
const int inf
=99999999;
using namespace std
;
struct edge
{
int u
,v
,w
;
}maze
[N
<<1];
int len
=1,head
[N
]={0};
int dep
[N
];
void add(int u
,int v
,int w
)
{
maze
[++len
]={head
[u
],v
,w
};
head
[u
]=len
;
}
int dfs(int u
,int f
,int t
)
{
int ans
=0,i
;
if(u
==t
)
return f
;
for(i
=head
[u
];i
&& f
;i
=maze
[i
].u
)
{
int v
=maze
[i
].v
,w
=maze
[i
].w
;
if(dep
[v
]==dep
[u
]+1 && w
)
{
int sum
=dfs(v
,min(f
,w
),t
);
maze
[i
].w
-=sum
;
maze
[i
^1].w
+=sum
;
f
-=sum
;
ans
+=sum
;
}
}
if(!ans
)
dep
[u
]=-2;
return ans
;
}
int bfs(int s
,int t
)
{
queue
<int> q
;
cl(dep
,0);
dep
[s
]=1;
q
.push(s
);
while(!q
.empty())
{
int u
=q
.front(),i
;
q
.pop();
for(i
=head
[u
];i
;i
=maze
[i
].u
)
{
int v
=maze
[i
].v
,w
=maze
[i
].w
;
if(w
&& !dep
[v
])
{
dep
[v
]=dep
[u
]+1;
q
.push(v
);
}
}
}
return dep
[t
];
}
int dinic(int s
,int t
)
{
int ans
=0;
while(bfs(s
,t
))
ans
+=dfs(s
,maxn
,t
);
return ans
;
}
signed main()
{
ios
::sync_with_stdio(false);
cin
.tie(0);cout
.tie(0);
int n
,i
;
cin
>>n
;
int s
=0,t
=3*n
+1;
for(i
=1;i
<=2*n
;i
++)
{
int x
,y
;
cin
>>x
>>y
;
add(s
,i
,1);
add(i
,s
,0);
add(i
,x
+2*n
,1);
add(x
+2*n
,i
,0);
add(i
,y
+2*n
,1);
add(y
+2*n
,i
,0);
}
for(i
=1;i
<=n
;i
++)
{
add(i
+2*n
,t
,2);
add(t
,i
+2*n
,0);
}
cout
<<dinic(s
,t
)<<endl
;
return 0;
}
