【总结向】个人赛补题 POJ - 3041 Asteroids ＆CodeForces - 173B Chamber of Secrets

url

POJ - 3041 Asteroids

大意：

N×N (1≤N≤500) 的网格，其中有 K (1≤K≤10000) 颗小行星。每次能够发射一道光束，将某行或者某列上的所有小行星轰成灰烬。希望发射的光束数量尽可能少。问发射的光束最少数量是多少？

思路：

没想到时那么那么那么裸的二分图匹配。。。

一直没有想到将每一个点的列和行作为二部图的两个顶点。

如果想到了这个的话，那其实就是要求一个图的最小覆盖，也就是最大匹配了。

然后匈牙利算法套板子即可。（有匈牙利谁还要写dinic。。。）

两小时罚坐买个教训

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define ll long long
const ll N=1e4+10;
struct ty{
	ll t,next;
}edge[N<<1];
ll cnt=0;
ll head[N];
ll n,m;
ll a,b;
void add(ll a,ll b)
{
	edge[++cnt].t=b;
	edge[cnt].next=head[a];
	head[a]=cnt;
}
ll t[N];
ll df[N];//匹配时间
ll match[N];//匹配对象
bool f(ll u,ll tim)
{
    for(int i=head[u];i!=-1;i=edge[i].next)
	{
		ll y=edge[i].t;
		if(df[y]==tim) continue;
		df[y]=tim;
		if(!match[y]||f(match[y],tim))
		{
			match[y]=u;
			return 1;
		}
	}	
	return 0;
} 
int main()
{
	memset(head,-1,sizeof head);
	cin>>n>>m;
	ll ti=0;
	for(int i=1;i<=m;++i)
	{
		cin>>a>>b;
		add(a,b);
		//add(b,a);
	}
	ll ans=0;
	for(int i=1;i<=n;++i)
	{
		if(f(i,++ti)) ans++;
	}
	cout<<ans<<endl;
	return 0;
 } 

事实上下一题也是同样的问题（一场比赛踩在同一个坑里两次也是没谁了）

url

大意：

初始在第一行，目标最后一行，问最少需要几个'#'进行转弯

思路:
一开始想到了最短路，但是建图的时候选择了最莽的方式。。。

我把每一行每一列的所有点两两连边，再把起点与第一行的所有点连接，把终点与最后一行的所有点连接，然后跑dijstra。苦哈哈敲了一百四十多行，超时了。。。然后花了半小时把T调成了wa

没谁了

跟上一题一样，如果选择将每一行/每一列缩成一个点的话，mp【i】【j】有一个石柱，就意味着可以从第i行跳到第j列，那么就是求第一行到第n行的最短路。代码就灰常简单了。

只是不知道为什么，我用链式前向星还是T，换成vector反而过了？？？

不懂。。。

#include<bits/stdc++.h>
#include<map>
#include<queue>
using namespace std;
#define ll int
#define lowbit(x) x&(-x)
const ll N=1010;
vector<ll> vt[N<<2];
ll vis[2020];
ll dis[2020];
ll n,m;
priority_queue<pair<ll,ll>> q;
inline void dij()
{
	for(int i=1;i<=n+m;++i) dis[i]=1e9;
	dis[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty())
	{
		ll ty=q.top().second;
		q.pop();
		if(vis[ty]++) continue;
		for(int i:vt[ty])
		{
			ll y=i;
			if(vis[y]) continue;
			if(dis[y]<=dis[ty]+1) continue;
			//cout<<edge[i].l<<endl;
			dis[y]=dis[ty]+1;
			if(y==n) return;
			q.push(make_pair(-dis[y],y));
		}
	}
}
char a;
char mp[N][N];
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	//memset(head,-1,sizeof head);
	ll num=0;
	for(int i=1;i<=n;++i)
	{
		cin>>(mp[i]+1);
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			//cout<<mp[i][j];
			if(mp[i][j]=='#')
			{
				vt[i].push_back(j+n);
				vt[j+n].push_back(i);
			}
		}
	//	cout<<endl;
	}
	dij(); 
	if(dis[n]<=1000000) cout<<dis[n];
	else cout<<-1;
	return 0;
}

总结：图论问题有时要考虑将行和列进行压缩，特别是当问题针对图中的某些点时