http://acm.sgu.ru/problem.php?contest=0&problem=318
看上去有点小难度。。实际上很水。。
一开始还想DP什么。。真是沙茶。。。
有两种方法。。一种从user的角度考虑。。每个user都有需要的快。。只要用类似矩形切割的办法。。不断取交集就OK了。。
还有一种从resource角度考虑。。两个resource可以合并成一组当且仅当需要他们的人是一样的。。用并差集实现就OK了。。当然要尽可能多的合并。。
PS为了实现方便。。可以利用集合pascal里面是set。。C++里面是bitset。。很方便的。。
Code。。。
#include<bitset>
#include<iostream>
using namespace std;
const int maxn=100+10;
int n,m,ans=0;
bitset<100> Q[maxn];
int F[maxn];
int find(int x)
{
if(F[x]!=x) F[x]=find(F[x]);
return F[x];
}
void Union(int x,int y)
{
x=find(x);y=find(y);
if(x!=y)
ans–;
F[x]=y;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) F[i]=i;
for(int i=0;i<m;i++)
{
int t,s;cin>>t;
while(t–)
{
cin>>s;s–;
Q[s][i]=true;
}
}
for(int i=0;i<n;i++) if(Q[i].count())
{
ans++;
for(int j=i+1;j<n;j++)
if(Q[i]==Q[j])
Union(i,j);
}
cout<<ans<<endl;
}