比赛链接：
http://acm.hdu.edu.cn/search.php?field=problem&key=2019+Multi-University+Training+Contest+1&source=1&searchmode=source
hdu6582
题意：
删除某些边，让$1$到$n$的最短路径发生变化
删除某条边的费用是边的长度
分析：
先用迪杰斯特拉跑一遍整个图，满足$dis[a]+w=dis[b]$的边，肯定是最短路径上的边
选出这些边，找到一个最小割集，Dinic比EK快很多，虽然渐进复杂度相同，都是$O(nm^2)$
Dinic加上弧优化后速度更快
ac代码(Dinic没有弧优化)：
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pa pair<ll,ll>
using namespace std;
const ll maxn=1e4+5;
const ll maxm=1e7+10;
const ll mod=1e9+7;
vector<pair<int,int>>ve[maxn];
ll dis[maxn];
int n,m,edge_num=-1,head[maxn],dep[maxn];
bool vis[maxn];
struct Edge{
int to,nex,v;
}edge[maxn*2];//maxn=1e4
void add_edge(int a,int b,int c)//边数从0开始，每次加上反向边，这样奇偶交替加边，重边无所谓
{
edge[++edge_num].to=b;
edge[edge_num].nex=head[a];
edge[edge_num].v=c;
head[a]=edge_num;
}
bool bfs()
{
for(int i=1;i<=n;i++)dep[i]=1e9;
dep[1]=0;
queue<int>que;
que.push(1);
while(que.size()){
int now=que.front();
que.pop();
for(int i=head[now];i!=-1;i=edge[i].nex){
int to=edge[i].to;
int v=edge[i].v;
if(v&&dep[to]>dep[now]+1){
dep[to]=dep[now]+1;
que.push(to);
}
}
}
if(dep[n]==1e9)return false;
else return true;
}
int dfs(int x,int lowflow)
{
if(x==n||lowflow==0)return lowflow;
int reslow=0;
int used=0;
for(int i=head[x];i!=-1;i=edge[i].nex){
int to=edge[i].to;
if(edge[i].v&&dep[x]+1==dep[to]){
if(reslow=dfs(to,min(lowflow,edge[i].v))){
edge[i].v-=reslow;
edge[i^1].v+=reslow;
used+=reslow;
lowflow-=reslow;
if(lowflow<=0)break;
}
}
}
return used;
}
void Dinic()
{
ll maxflow=0;
int lowflow;
while(bfs()){
while(lowflow=dfs(1,1e9)){
maxflow+=lowflow;
}
}
printf("%lld
",maxflow);
}
void dj()
{
for(int i=1;i<=n;i++)dis[i]=1e18,vis[i]=false;
dis[1]=0;
priority_queue<pair<ll,int>>que;
que.push(make_pair(0,1));
while(que.size()){
pair<ll,int>now=que.top();
que.pop();
if(vis[now.second])continue;
vis[now.second]=true;
for(int i=0;i<ve[now.second].size();i++){
int to=ve[now.second][i].first;
int w=ve[now.second][i].second;
if(dis[to]>dis[now.second]+w){
dis[to]=dis[now.second]+w;
que.push(make_pair(-dis[to],to));
}
}
}
}
int main()
{
// freopen("D:/a.txt","w",stdout);
// freopen("D:/2.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
ve[a].push_back(make_pair(b,c));
}
dj();
if(dis[n]==1e18){
printf("0
");
continue;
}
for(int i=1;i<=n;i++)head[i]=-1;
edge_num=-1;
for(int i=1;i<=n;i++){
for(int j=0;j<ve[i].size();j++){
int a=i,b=ve[i][j].first,c=ve[i][j].second;
if(dis[a]+c==dis[b])add_edge(a,b,c),add_edge(b,a,0);
}
}
Dinic();
for(int i=1;i<=n;i++)ve[i].clear();
}
return 0;
}
ac代码(Dinic弧优化)：
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pa pair<ll,ll>
using namespace std;
const ll maxn=1e4+5;
const ll maxm=1e7+10;
const ll mod=1e9+7;
vector<pair<int,int>>ve[maxn];
ll dis[maxn];
int n,m,edge_num=-1,head[maxn],dep[maxn],cur[maxn];
bool vis[maxn];
struct Edge{
int to,nex,v;
}edge[maxn*2];//maxn=1e4
void add_edge(int a,int b,int c)//边数从0开始，每次加上反向边，这样奇偶交替加边，重边无所谓
{
edge[++edge_num].to=b;
edge[edge_num].nex=head[a];
edge[edge_num].v=c;
head[a]=edge_num;
}
bool bfs()//分层
{
for(int i=1;i<=n;i++)dep[i]=1e9;
dep[1]=0;
queue<int>que;
que.push(1);
while(que.size()){
int now=que.front();
que.pop();
for(int i=head[now];i!=-1;i=edge[i].nex){
int to=edge[i].to;
int v=edge[i].v;
if(v&&dep[to]>dep[now]+1){
dep[to]=dep[now]+1;
que.push(to);
}
}
}
if(dep[n]==1e9)return false;
else return true;
}
int dfs(int x,int lowflow)
{
if(x==n||lowflow==0)return lowflow;
int reslow=0;
int used=0;
for(int &i=cur[x];i!=-1;i=edge[i].nex){
int to=edge[i].to;
if(edge[i].v&&dep[x]+1==dep[to]){
if(reslow=dfs(to,min(lowflow,edge[i].v))){
edge[i].v-=reslow;
edge[i^1].v+=reslow;
used+=reslow;
lowflow-=reslow;
if(lowflow<=0)break;
}
}
}
return used;
}
void Dinic()
{
ll maxflow=0;
int lowflow;
while(bfs()){
for(int i=1;i<=n;i++)cur[i]=head[i];
while(lowflow=dfs(1,1e9)){
maxflow+=lowflow;
}
}
printf("%lld
",maxflow);
}
void dj()
{
for(int i=1;i<=n;i++)dis[i]=1e18,vis[i]=false;
dis[1]=0;
priority_queue<pair<ll,int>>que;
que.push(make_pair(0,1));
while(que.size()){
pair<ll,int>now=que.top();
que.pop();
if(vis[now.second])continue;
vis[now.second]=true;
for(int i=0;i<ve[now.second].size();i++){
int to=ve[now.second][i].first;
int w=ve[now.second][i].second;
if(dis[to]>dis[now.second]+w){
dis[to]=dis[now.second]+w;
que.push(make_pair(-dis[to],to));
}
}
}
}
int main()
{
// freopen("D:/a.txt","w",stdout);
// freopen("D:/2.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
ve[a].push_back(make_pair(b,c));
}
dj();
if(dis[n]==1e18){
printf("0
");
continue;
}
for(int i=1;i<=n;i++)head[i]=-1;
edge_num=-1;
for(int i=1;i<=n;i++){
for(int j=0;j<ve[i].size();j++){
int a=i,b=ve[i][j].first,c=ve[i][j].second;
if(dis[a]+c==dis[b])add_edge(a,b,c),add_edge(b,a,0);
}
}
Dinic();
for(int i=1;i<=n;i++)ve[i].clear();
}
return 0;
}
hdu6581
题意：
给出车子的位置，长度，最大速度，不能超车，求最后面车子的最快通过时间
分析：
对于时间$t$，最前面的车因为没有阻挡，可以直接得到它的位置，第二辆车，要么粘在上一辆车后面，要么以自己的速度运行$t$时间
对时间二分，可以得到每辆车的位置，验证最后一辆车的位置即可
ac代码：
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pa pair<ll,ll>
using namespace std;
const ll maxn=1e5+5;
const ll maxm=1e7+10;
const ll mod=1e9+7;
double pos[maxn];
int s[maxn],l[maxn],v[maxn],n;
bool check(double t)
{
pos[n]=s[n]-t*v[n];
for(int i=n-1;i>=0;i--){
pos[i]=max(s[i]-t*v[i],pos[i+1]+l[i+1]);
}
if(pos[0]<0)return true;
return false;
}
int main()
{
while(scanf("%d",&n)==1){
for(int i=0;i<=n;i++)scanf("%d",&l[i]);
for(int i=0;i<=n;i++)scanf("%d",&s[i]);
for(int i=0;i<=n;i++)scanf("%d",&v[i]);
double st=0,en=1e9;
for(int i=1;i<=100;i++){
double md=(st+en)/2;
if(check(md))en=md;
else st=md;
}
printf("%.10f
",st);
}
return 0;
}
hdu6579
题意：
有两种操作，1，在数组最后添加一位，2，求区间的最大异或和
分析：
如果对每个区间求一次线性基，肯定超时
我们可以求出一个前缀线性基，不同的是，如果$b[i]$(线性基数组)位置已经有一个数，我们把位置大的数放进去，并且拿出$b[i]$
对于每次询问，我们只需要看这个基底位置是不是大于$l$即可
ac代码：
#include<bits/stdc++.h>
#define ll long long
#define PI acos(-1.0)
#define pa pair<int,int>
using namespace std;
const int maxn=1e6+10;
const ll mod=1e9+7;
pa b[31],base[maxn][31];
void add(int x,int pos)
{
for(int i=30;i>=1;i--){
if(x&(1<<(i-1))){
if(b[i].first==0){
b[i].first=x;
b[i].second=pos;
break;
}
if(pos>b[i].second){//核心代码，每次保留位置最大的基
swap(pos,b[i].second);
swap(x,b[i].first);
}
x^=b[i].first;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
for(int i=1;i<=30;i++)b[i]=make_pair(0,0);
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
add(x,i);
for(int j=1;j<=30;j++)base[i][j]=b[j];
}
int lastan=0;
for(int i=1;i<=m;i++){
int comd,l,r;
scanf("%d",&comd);
if(comd){
scanf("%d",&l);
l^=lastan;
add(l,++n);
for(int j=1;j<=30;j++)base[n][j]=b[j];
}else{
scanf("%d %d",&l,&r);
l=(l^lastan)%n+1,r=(r^lastan)%n+1;
if(l>r)swap(l,r);
lastan=0;
for(int j=30;j>=1;j--)
if(base[r][j].second>=l)
lastan=max(lastan,lastan^base[r][j].first);
printf("%d
",lastan);
}
}
}
return 0;
}